{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Path to Get All Keys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestPathAllKeys"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #获取所有钥匙的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二维网格&nbsp;<code>grid</code>&nbsp;，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">'.'</span></span></font></font> 代表一个空房间</li>\n",
    "\t<li><font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">'#'</span></span></font></font> 代表一堵墙</li>\n",
    "\t<li><font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">'@'</span></span></font></font>&nbsp;是起点</li>\n",
    "\t<li>小写字母代表钥匙</li>\n",
    "\t<li>大写字母代表锁</li>\n",
    "</ul>\n",
    "\n",
    "<p>我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。</p>\n",
    "\n",
    "<p>假设 k&nbsp;为 钥匙/锁 的个数，且满足&nbsp;<code>1 &lt;= k&nbsp;&lt;= 6</code>，字母表中的前 <code>k</code>&nbsp;个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。</p>\n",
    "\n",
    "<p>返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-keys2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [\"@.a.#\",\"###.#\",\"b.A.B\"]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>目标是获得所有钥匙，而不是打开所有锁。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-key2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [\"@..aA\",\"..B#.\",\"....b\"]\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-keys3.jpg\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [\"@Aa\"]\n",
    "<strong>输出:</strong> -1</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 30</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;只含有&nbsp;<code>'.'</code>,&nbsp;<code>'#'</code>,&nbsp;<code>'@'</code>,&nbsp;<code>'a'-</code><code>'f</code><code>'</code>&nbsp;以及&nbsp;<code>'A'-'F'</code></li>\n",
    "\t<li>钥匙的数目范围是&nbsp;<code>[1, 6]</code>&nbsp;</li>\n",
    "\t<li>每个钥匙都对应一个 <strong>不同</strong> 的字母</li>\n",
    "\t<li>每个钥匙正好打开一个对应的锁</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-path-to-get-all-keys](https://leetcode.cn/problems/shortest-path-to-get-all-keys/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-path-to-get-all-keys](https://leetcode.cn/problems/shortest-path-to-get-all-keys/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"@.a..\",\"###.#\",\"b.A.B\"]', '[\"@..aA\",\"..B#.\",\"....b\"]', '[\"@Aa\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        d = [1, 0, -1, 0, 1]\n",
    "        n, m, keys = len(grid), len(grid[0]), 0\n",
    "        start = [0] * 4\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '@':\n",
    "                    start[0], start[1] = i, j\n",
    "                # 统计存在几个钥匙\n",
    "                if grid[i][j].islower():\n",
    "                    keys += 1\n",
    "\n",
    "        v = [[[False] * (1 << keys) for _ in range(m)]for _ in range(n)]\n",
    "        q = deque([start])\n",
    "        v[0][0][0] = True\n",
    "        while q:\n",
    "            a = q.popleft()\n",
    "            i, j, k, step = a[0], a[1], a[2], a[3]\n",
    "            # 获取了所有钥匙\n",
    "            if k == ((1 << keys) - 1):\n",
    "                return step\n",
    "            for d0 in range(4):\n",
    "                i2, j2, k2 = i + d[d0], j + d[d0 + 1], k\n",
    "                if 0 <= i2 < n and 0 <= j2 < m:\n",
    "                    c = grid[i2][j2]\n",
    "                    # 墙\n",
    "                    if c == '#':\n",
    "                        continue\n",
    "                    # 找到钥匙，可以不修改cs[i2][j2]的状态，直接按位或即可\n",
    "                    # 注意这里不能直接修改k,而是要用k2接收k，否则遍历其他位置时，造成“隔空取钥匙”导致步数缩短\n",
    "                    if c.islower():\n",
    "                        k2 |= (1 << (ord(c) - ord('a')))\n",
    "                    # 遇到锁，没有钥匙\n",
    "                    if c.isupper() and (k2 & (1 << (ord(c) - ord('A')))) == 0:\n",
    "                        continue\n",
    "                    # 该状态之前访问过\n",
    "                    if v[i2][j2][k2]:\n",
    "                        continue\n",
    "                    v[i2][j2][k2] = True\n",
    "                    q.append([i2, j2, k2, step + 1])\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        d = [1, 0, -1, 0, 1]\n",
    "        n,m,keys=len(grid),len(grid[0]),0\n",
    "        start=[0]*4\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]==\"@\":\n",
    "                    start[0],start[1]=i,j\n",
    "                if grid[i][j].islower():\n",
    "                    keys+=1\n",
    "\n",
    "        v = [[[False] * (1 << keys) for _ in range(m)] for _ in range(n)]\n",
    "        q=deque([start])\n",
    "        v[0][0][0]=True\n",
    "        while q:\n",
    "            a=q.popleft()\n",
    "            i,j,k,step=a[0],a[1],a[2],a[3]\n",
    "            if k==((1<<keys)-1):\n",
    "                return step \n",
    "            \n",
    "            for d0 in range(4):\n",
    "                i2,j2,k2=i+ d[d0],j+d[d0+1],k\n",
    "                if 0<=i2<n and 0<=j2<m:\n",
    "                    c=grid[i2][j2]\n",
    "                    \n",
    "                    if c==\"#\":\n",
    "                        continue\n",
    "                    \n",
    "                    if c.islower():\n",
    "                        k2|=(1<<(ord(c)-ord('a')))\n",
    "                    if c.isupper()and (k2&(1<<(ord(c)-ord('A'))))==0:\n",
    "                        continue\n",
    "                    if v[i2][j2][k2]:\n",
    "                        continue\n",
    "                    v[i2][j2][k2]=True\n",
    "                    q.append([i2,j2,k2,step+1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        key = 0\n",
    "        start = 0\n",
    "        cnt = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    start = (i, j)\n",
    "                if 'a' <= grid[i][j] <= 'z':\n",
    "                    key |= 1 << (ord(grid[i][j]) - ord('a'))\n",
    "                    cnt += 1\n",
    "        vis = [[[False] * 2 ** cnt for _ in range(n)] for _ in range(m)]\n",
    "        q = [(start[0], start[1], 0)]\n",
    "        steps = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            steps += 1\n",
    "            for i, j, state in tmp:\n",
    "                for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                    new_state = state\n",
    "                    if x < 0 or x == m or y < 0 or y == n or grid[x][y] == '#':\n",
    "                        continue\n",
    "                    if 'A' <= grid[x][y] <= 'Z' and (1 & state >> (ord(grid[x][y]) - ord('A')) == 0):\n",
    "                        continue\n",
    "                    if 'a' <= grid[x][y] <= 'z':\n",
    "                        new_state |= 1 << (ord(grid[x][y]) - ord('a'))\n",
    "                    if new_state == key:\n",
    "                        return steps\n",
    "                    if not vis[x][y][new_state]:\n",
    "                        vis[x][y][new_state] = True\n",
    "                        q.append((x, y, new_state))\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        \n",
    "                \n",
    "                \n",
    "                def cxk(x):\n",
    "                    if 'a' <= x <= 'z':return 1\n",
    "                    if 'A' <= x <= 'Z':return 2\n",
    "                    return 3\n",
    "                m = len(grid);n = len(grid[0])\n",
    "                f = [[[inf for k in range(1<<6)] for j in range(n)] for i in range(m)]\n",
    "                q = deque();cnt =0 \n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        if grid[i][j] == '@':\n",
    "                            q.append([i,j,0])\n",
    "                            f[i][j][0] = 0\n",
    "                        elif grid[i][j].islower():\n",
    "                            cnt += 1\n",
    "               \n",
    "                while q:\n",
    "                    i,j,key = q.popleft()\n",
    "                    step = f[i][j][key]\n",
    "                    \n",
    "                    for dx,dy in [[1,0],[0,1],[0,-1],[-1,0]]:\n",
    "                        x = i + dx;y = j + dy\n",
    "                        if x < 0 or x == m or y < 0 or y == n or grid[x][y] == '#':continue\n",
    "                        p = cxk(grid[x][y]);c = grid[x][y]\n",
    "                        if p ==2 and (key >> (ord(c) - ord('A'))) & 1 == 0:\n",
    "                            continue\n",
    "                       \n",
    "                        nk = key\n",
    "                        if p == 1:\n",
    "                            nk  |=  (1<<(ord(c) - ord('a')))\n",
    "                        if nk + 1 == 1<<cnt:\n",
    "                            return step + 1\n",
    "\n",
    "                        if f[x][y][nk] <= step + 1:continue\n",
    "                        q.append([x,y,nk])\n",
    "                        f[x][y][nk] = min(step + 1,f[x][y][nk])\n",
    "                                    \n",
    "                return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        q = deque()\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        num = 0\n",
    "        # 走到 (i, j)，且状态为 s 时的最小步数，状态每一位代表有无钥匙\n",
    "        dist = [[[inf for _ in range(1 << 6)] for _ in range(m)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '@':\n",
    "                    dist[i][j][0] = 0\n",
    "                    q.append([i, j, 0])\n",
    "                elif grid[i][j] >= 'A' and grid[i][j] <= 'F':\n",
    "                    num += 1\n",
    "        dxy = [[-1, 0], [1, 0], [0, 1], [0, -1]]\n",
    "        while q:\n",
    "            # state 保留当前状态\n",
    "            x, y, state = q.popleft()\n",
    "            # 获得到 (x, y) 位置的移动次数\n",
    "            d = dist[x][y][state]\n",
    "            for dx, dy in dxy:\n",
    "                a, b, s = x + dx, y + dy, state\n",
    "                if a < 0 or a >= n or b < 0 or b >= m or grid[a][b] == '#':\n",
    "                    continue\n",
    "                c = grid[a][b]\n",
    "                # 锁，没钥匙\n",
    "                if c.isupper() and s & (1 << (ord(c) - ord('A'))) == 0:\n",
    "                    continue\n",
    "                # 钥匙\n",
    "                if c.islower():\n",
    "                    # 修改的是新状态 s\n",
    "                    s |= 1 << (ord(c) - ord('a'))\n",
    "                if dist[a][b][s] > d + 1:\n",
    "                    dist[a][b][s] = d + 1\n",
    "                    q.append([a, b, s])\n",
    "                # 找到了全部钥匙\n",
    "                if s == (1 << num) - 1:\n",
    "                    return d + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        tot = 0\n",
    "        q = deque() \n",
    "        dist = [[[inf] * 100 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    dist[i][j][0] = 0\n",
    "                    q.append((i,j,0))\n",
    "                elif grid[i][j].islower():\n",
    "                    tot += 1\n",
    "        while q:\n",
    "            x, y, st = q.popleft()\n",
    "            for nx, ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if not (0 <= nx < m and 0 <= ny < n):\n",
    "                    continue\n",
    "                ch = grid[nx][ny]\n",
    "                if ch == '#':\n",
    "                    continue\n",
    "                if ch.isupper() and (st >> (ord(ch) - ord('A'))) & 1 == 0:\n",
    "                    continue\n",
    "                nst = st\n",
    "                if ch.islower():\n",
    "                    nst |= 1 << (ord(ch) - ord('a'))\n",
    "                if nst.bit_count() == tot:\n",
    "                    return dist[x][y][st] + 1\n",
    "                if dist[x][y][st] + 1 >= dist[nx][ny][nst]:\n",
    "                    continue\n",
    "                dist[nx][ny][nst] = dist[x][y][st] + 1\n",
    "                q.append((nx,ny,nst))\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\r\n",
    "        m = len(grid)\r\n",
    "        n = len(grid[0])\r\n",
    "        tgt = 0\r\n",
    "        q: deque[tuple[int, int, int, int]] = deque()\r\n",
    "        visited: list[list[set[int]]] = [[set() for _ in range(n)] for __ in range(m)]\r\n",
    "        neighbors = [(-1, 0), (1, 0), (0, -1), (0, 1)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == '@':\r\n",
    "                    visited[i][j].add(0)\r\n",
    "                    q.append((0, 0, i, j))\r\n",
    "                elif grid[i][j].islower():\r\n",
    "                    tgt |= 1 << (ord(grid[i][j]) - 97)\r\n",
    "        \r\n",
    "        while q:\r\n",
    "            key, dist, i, j = q.popleft()\r\n",
    "            if grid[i][j].islower():\r\n",
    "                key |= 1 << (ord(grid[i][j]) - 97)\r\n",
    "                if key == tgt: return dist\r\n",
    "            for a, b in neighbors:\r\n",
    "                if 0 <= i + a < m and 0 <= j + b < n and \\\r\n",
    "                    grid[i + a][j + b] != '#' and \\\r\n",
    "                    (not grid[i + a][j + b].isupper() or key >> (ord(grid[i + a][j + b]) - 65) & 1) and \\\r\n",
    "                    key not in visited[i + a][j + b]:\r\n",
    "                    visited[i + a][j + b].add(key)\r\n",
    "                    q.append((key, dist + 1, i + a, j + b))\r\n",
    "        \r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\r\n",
    "        m = len(grid)\r\n",
    "        n = len(grid[0])\r\n",
    "        tgt = 0\r\n",
    "        q: deque[tuple[int, int, int, int]] = deque()\r\n",
    "        visited: list[list[set[int]]] = [[set() for _ in range(n)] for __ in range(m)]\r\n",
    "        neighbors = [(-1, 0), (1, 0), (0, -1), (0, 1)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == '@':\r\n",
    "                    visited[i][j].add(0)\r\n",
    "                    q.append((0, 0, i, j))\r\n",
    "                elif grid[i][j].islower():\r\n",
    "                    tgt |= 1 << (ord(grid[i][j]) - 97)\r\n",
    "        \r\n",
    "        while q:\r\n",
    "            key, dist, i, j = q.popleft()\r\n",
    "            if grid[i][j].islower():\r\n",
    "                key |= 1 << (ord(grid[i][j]) - 97)\r\n",
    "                if key == tgt: return dist\r\n",
    "            for a, b in neighbors:\r\n",
    "                if 0 <= i + a < m and 0 <= j + b < n and \\\r\n",
    "                    grid[i + a][j + b] != '#' and \\\r\n",
    "                    (not grid[i + a][j + b].isupper() or key >> (ord(grid[i + a][j + b]) - 65) & 1) and \\\r\n",
    "                    all((v | key) != v for v in visited[i + a][j + b]):\r\n",
    "                    visited[i + a][j + b].add(key)\r\n",
    "                    q.append((key, dist + 1, i + a, j + b))\r\n",
    "        \r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        max_key = 'a'\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    start_x = i\n",
    "                    start_y = j\n",
    "                elif grid[i][j] != '#' and grid[i][j] != '.':\n",
    "                    if grid[i][j] > max_key:\n",
    "                        max_key = grid[i][j]\n",
    "        \n",
    "        key_num = ord(max_key) - 96\n",
    "        used = [[[False] * (1 << key_num) for _ in range(n)] for _ in range(m)]\n",
    "        used[start_x][start_y][0] = True\n",
    "        q = [[start_x, start_y, 0]]\n",
    "        l = 0\n",
    "        r = 1\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "        step = 0\n",
    "        while l < r:\n",
    "            step += 1\n",
    "            for nowx, nowy, now_state in q[l:r]:\n",
    "                for index in range(4):\n",
    "                    x = nowx + dx[index]\n",
    "                    y = nowy + dy[index]\n",
    "                    if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] != '#':\n",
    "                        if grid[x][y] == '.' or grid[x][y] == '@':\n",
    "                            if not used[x][y][now_state]:\n",
    "                                q.append([x, y, now_state])\n",
    "                                used[x][y][now_state] = True\n",
    "                        elif grid[x][y] >= 'a' and grid[x][y] <= max_key:\n",
    "                            state = now_state | (1 << (ord(grid[x][y]) - 97))\n",
    "                            if state == (1 << key_num) - 1:\n",
    "                                return step\n",
    "                            if not used[x][y][state]:\n",
    "                                q.append([x, y, state])\n",
    "                                used[x][y][state] = True\n",
    "                        elif (now_state & (1 << (ord(grid[x][y]) - 65))) and not used[x][y][now_state]:\n",
    "                                q.append([x, y, now_state])\n",
    "                                used[x][y][now_state] = True\n",
    "\n",
    "            l, r = r, len(q)\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        cnt = 0\n",
    "        dis = defaultdict(lambda: 0x3f3f3f3f)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '@':\n",
    "                    q = deque([(i, j, 0)])\n",
    "                    dis[(i, j, 0)] = 0\n",
    "                elif grid[i][j].islower():\n",
    "                    cnt += 1\n",
    "\n",
    "\n",
    "        dx = [0,1,0,-1]\n",
    "        dy = [1,0,-1,0]\n",
    "        \n",
    "        \n",
    "        while q:\n",
    "            i, j, cur = q.popleft()\n",
    "            step = dis[(i,  j, cur)]\n",
    "            for k in range(4):\n",
    "                ni, nj = i + dx[k], j + dy[k]\n",
    "                if 0 <= ni < n and 0 <= nj < m:\n",
    "                    c = grid[ni][nj]\n",
    "                    if c == '#':\n",
    "                        continue\n",
    "                    # 先将cur右移c位然后&1判断是否为1\n",
    "                    if 'A' <= c <= 'Z' and (cur >> (ord(c) - ord('A')) & 1) == 0:\n",
    "                        continue\n",
    "                    ncur = cur\n",
    "                    if 'a' <= c <= 'z':\n",
    "                        # 标记为已有\n",
    "                        ncur |= (1 << ord(c) - ord('a'))\n",
    "                    if ncur == (1 << cnt) - 1:\n",
    "                        return step + 1\n",
    "                    # \n",
    "                    if step + 1 < dis[(ni, nj, ncur)]:\n",
    "                        dis[(ni, nj, ncur)] = step + 1\n",
    "                        q.append((ni, nj, ncur))\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m,n,cnt = len(grid),len(grid[0]),0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    q = [(i,j,0)]\n",
    "                elif 'a'<= grid[i][j] <= 'z':\n",
    "                    cnt+=1\n",
    "        step = 0\n",
    "        dist = defaultdict(lambda : 0x3f3f3f3f)\n",
    "        while q:\n",
    "            t = q\n",
    "            q = []\n",
    "            for x,y,key in t:\n",
    "                for nx,ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                    if m>nx>=0<=ny<n:\n",
    "                        c = grid[nx][ny]\n",
    "                        if c == '#':\n",
    "                            continue\n",
    "                        if 'A' <= c <= 'Z' and (key >> (ord(c)-ord('A')) & 1) == 0:\n",
    "                            continue\n",
    "                        nkey = key\n",
    "                        if 'a' <= c <= 'z':\n",
    "                            nkey |= (1<<(ord(c)-ord('a')))\n",
    "                        if nkey == (1<<cnt)-1:\n",
    "                            return step+1\n",
    "                        if step + 1 >= dist[(nx, ny, nkey)]:\n",
    "                            continue\n",
    "                        dist[(nx, ny, nkey)] = step + 1\n",
    "                        q.append((nx,ny,nkey))\n",
    "            step +=1\n",
    "        return -1\n",
    "                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        dist, key, q = collections.defaultdict(lambda: math.inf), 0, collections.deque()\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        d = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if 'a' <= grid[i][j] <= 'z':\n",
    "                    key += 1\n",
    "                elif grid[i][j] == '@':\n",
    "                    q.append((i, j, 0))\n",
    "                    dist[(i, j, 0)] = 0\n",
    "        while q:\n",
    "            x, y, cur = q.popleft()\n",
    "            step = dist[(x, y, cur)]\n",
    "            for tx, ty in d:\n",
    "                nx, ny = x + tx, y + ty\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m:\n",
    "                    continue\n",
    "                c = grid[nx][ny]\n",
    "                if c == '#':\n",
    "                    continue\n",
    "                if 'A' <= c <= 'Z' and (cur >> (ord(c) - ord('A')) & 1) == 0:\n",
    "                    continue\n",
    "                ncur = cur\n",
    "                if 'a' <= c <= 'z':\n",
    "                    ncur |= (1 << (ord(c) - ord('a')))\n",
    "                if ncur == (1 << key) - 1:\n",
    "                    return step + 1\n",
    "                \n",
    "                if step + 1 >= dist[(nx, ny, ncur)]:\n",
    "                    continue\n",
    "                dist[(nx, ny, ncur)] = step + 1\n",
    "                q.append((nx, ny, ncur))\n",
    "                \n",
    "        return -1\n",
    "                \n",
    "                    \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, g: List[str]) -> int:\n",
    "        dirs = [[0,1], [0,-1], [1,0], [-1,0]]\n",
    "        n, m, cnt = len(g), len(g[0]), 0\n",
    "        dist = defaultdict(lambda : 0x3f3f3f3f)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                c = g[i][j]\n",
    "                if c == '@':\n",
    "                    d = deque([(i, j, 0)])\n",
    "                    dist[(i, j, 0)] = 0\n",
    "                elif 'a' <= c <= 'z':\n",
    "                    cnt += 1\n",
    "        while d:\n",
    "            x, y, cur = d.popleft()\n",
    "            step = dist[(x, y, cur)]\n",
    "            for di in dirs:\n",
    "                nx, ny = x + di[0], y + di[1]\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m:\n",
    "                    continue\n",
    "                c = g[nx][ny]\n",
    "                if c == '#':\n",
    "                    continue\n",
    "                if 'A' <= c <= 'Z' and (cur >> (ord(c) - ord('A')) & 1) == 0:\n",
    "                    continue\n",
    "                ncur = cur\n",
    "                if 'a' <= c <= 'z':\n",
    "                    ncur |= (1 << (ord(c) - ord('a')))\n",
    "                if ncur == (1 << cnt) - 1:\n",
    "                    return step + 1\n",
    "                if step + 1 >= dist[(nx, ny, ncur)]:\n",
    "                    continue\n",
    "                dist[(nx, ny, ncur)] = step + 1\n",
    "                d.append((nx, ny, ncur))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, g: List[str]) -> int:\n",
    "        dirs = [[0,1], [0,-1], [1,0], [-1,0]]\n",
    "        n, m, cnt = len(g), len(g[0]), 0\n",
    "        dist = defaultdict(lambda : 0x3f3f3f3f)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                c = g[i][j]\n",
    "                if c == '@':\n",
    "                    d = deque([(i, j, 0)])\n",
    "                    dist[(i, j, 0)] = 0\n",
    "                elif 'a' <= c <= 'z':\n",
    "                    cnt += 1\n",
    "        while d:\n",
    "            x, y, cur = d.popleft()\n",
    "            step = dist[(x, y, cur)]\n",
    "            for di in dirs:\n",
    "                nx, ny = x + di[0], y + di[1]\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m:\n",
    "                    continue\n",
    "                c = g[nx][ny]\n",
    "                if c == '#':\n",
    "                    continue\n",
    "                if 'A' <= c <= 'Z' and (cur >> (ord(c) - ord('A')) & 1) == 0:\n",
    "                    continue\n",
    "                ncur = cur\n",
    "                if 'a' <= c <= 'z':\n",
    "                    ncur |= (1 << (ord(c) - ord('a')))\n",
    "                if ncur == (1 << cnt) - 1:\n",
    "                    return step + 1\n",
    "                if step + 1 >= dist[(nx, ny, ncur)]:\n",
    "                    continue\n",
    "                dist[(nx, ny, ncur)] = step + 1\n",
    "                d.append((nx, ny, ncur))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m,n,cnt = len(grid),len(grid[0]),0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    q = [(i,j,0)]\n",
    "                elif 'a'<= grid[i][j] <= 'z':\n",
    "                    cnt+=1\n",
    "        step = 0\n",
    "        dist = defaultdict(lambda : 0x3f3f3f3f)\n",
    "        while q:\n",
    "            t = q\n",
    "            q = []\n",
    "            for x,y,key in t:\n",
    "                print(x,y,key)\n",
    "                for nx,ny in (x+1,y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                    if m>nx>=0<=ny<n:\n",
    "                        c = grid[nx][ny]\n",
    "                        if c == '#':\n",
    "                            continue\n",
    "                        if 'A' <= c <= 'Z' and (key >> (ord(c)-ord('A')) & 1) == 0:\n",
    "                            continue\n",
    "                        nkey = key\n",
    "                        if 'a' <= c <= 'z':\n",
    "                            nkey |= (1<<(ord(c)-ord('a')))\n",
    "                        if nkey == (1<<cnt)-1:\n",
    "                            return step+1\n",
    "                        if step + 1 >= dist[(nx, ny, nkey)]:\n",
    "                            continue\n",
    "                        dist[(nx, ny, nkey)] = step + 1\n",
    "                        q.append((nx,ny,nkey))\n",
    "            step +=1\n",
    "        return -1\n",
    "                            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx, sy = None, None\n",
    "        keycnt = 0\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].islower():\n",
    "                    keycnt += 1\n",
    "        \n",
    "        q = deque([(sx, sy, 0)])\n",
    "        move = {}\n",
    "        move[(sx, sy, 0)] = 0\n",
    "\n",
    "        while q:\n",
    "            x, y, keys = q.popleft()\n",
    "            _m = move[(x, y, keys)]\n",
    "            _m += 1\n",
    "            \n",
    "            for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if 0 <= i < m and 0 <= j < n and grid[i][j] != '#':\n",
    "                    if grid[i][j].isupper() and keys & 1 << (ord(grid[i][j])- ord('A')) == 0:\n",
    "                        continue\n",
    "                    new_key = keys\n",
    "                    if grid[i][j].isalpha() and grid[i][j].islower():\n",
    "                        new_key |= 1 << (ord(grid[i][j]) - ord('a'))\n",
    "                        if new_key == (1 << keycnt) - 1:\n",
    "                            return _m\n",
    "\n",
    "                    if (i, j, new_key) not in move:\n",
    "                        q.append((i, j, new_key))\n",
    "                        move[(i, j, new_key)] = _m\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#用最小keys个二进制位标记不同钥匙的收集情况\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        keys=0\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dq=deque()\n",
    "        k=defaultdict(lambda : 0x3f3f3f3f)  #记录到达各个位置收集到不同钥匙数所需要的最少步数\n",
    "        #进行一次遍历，找出起点和所有钥匙的位置\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c=grid[i][j]\n",
    "                if c=='@':\n",
    "                    dq.append((i,j,0))\n",
    "                    k[(i,j,0)]=0    #起点移动步数为0\n",
    "                elif 'a'<=c<='z':\n",
    "                    keys+=1\n",
    "        #BFS、按步数从小到大枚举\n",
    "        while dq:\n",
    "            x0,y0,collections=dq.popleft()\n",
    "            steps=k[(x0,y0,collections)]\n",
    "            for x,y in [(x0+1,y0),(x0,y0+1),(x0,y0-1),(x0-1,y0)]:\n",
    "                if x<0 or x>=m or y<0 or y>=n:\n",
    "                    continue\n",
    "                p=grid[x][y]\n",
    "                if p=='#':#遇到墙\n",
    "                    continue\n",
    "                if 'A'<=p<='Z' and (collections>>(ord(p)-ord('A'))&1)==0:#遇到锁具但没有对应钥匙\n",
    "                    continue\n",
    "                newcollections=collections\n",
    "                if 'a'<=p<='z':#标记获得钥匙\n",
    "                    newcollections|=1<<(ord(p)-ord('a'))\n",
    "                if newcollections==(1<<keys)-1:#集齐了所有钥匙\n",
    "                    return steps+1\n",
    "                if steps+1>=k[(x,y,newcollections)]:\n",
    "                    continue\n",
    "                k[(x,y,newcollections)]=steps+1 #记录到达[x,y]位置且获得相应newcollections状态钥匙数需要的最少步数\n",
    "                dq.append((x,y,newcollections))\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0]) # work hard\n",
    "        ind_dict = dict()\n",
    "        sx, sy = -1, -1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if 'a' <= grid[i][j] <= 'z':\n",
    "                    if grid[i][j] not in ind_dict:\n",
    "                        ind_dict[grid[i][j]] = len(ind_dict)\n",
    "                elif grid[i][j] == '@':\n",
    "                    sx, sy = i, j\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] # 广度优先遍历\n",
    "        dist = dict()\n",
    "        dist[(sx, sy, 0)] = 0\n",
    "        q = [(sx, sy, 0)]\n",
    "        while q:\n",
    "            x, y, mask = q.pop(0)\n",
    "            for di in dirs: # 碰见空房间\n",
    "                curx, cury = di[0] + x, di[1] + y\n",
    "                if 0 <= curx < m and 0 <= cury < n and grid[curx][cury] != '#':\n",
    "                    if grid[curx][cury] == '.' or grid[curx][cury] == '@':\n",
    "                        if (curx, cury, mask) not in dist: # 记录访问过的点\n",
    "                            dist[(curx, cury, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((curx, cury, mask))\n",
    "                    elif grid[curx][cury].islower(): # 碰见钥匙\n",
    "                        ind = ind_dict[grid[curx][cury]]\n",
    "                        if (curx, cury, mask | (1 << ind)) not in dist:\n",
    "                            dist[(curx, cury, mask | (1 << ind))] = dist[(x, y, mask)] + 1\n",
    "                            if (mask | (1 << ind)) == (1 << len(ind_dict)) - 1:\n",
    "                                return dist[(curx, cury, mask | (1 << ind))]\n",
    "                            q.append((curx, cury, mask | (1 << ind)))\n",
    "                    else: # 碰见锁\n",
    "                        ind = ind_dict[grid[curx][cury].lower()]\n",
    "                        if ((1 << ind) & mask) and (curx, cury, mask) not in dist:\n",
    "                            dist[(curx, cury, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((curx, cury, mask))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx, sy = None, None\n",
    "        keycnt = 0\n",
    "\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].islower():\n",
    "                    keycnt += 1\n",
    "        \n",
    "        q = deque([(sx, sy, 0)])\n",
    "        move = {}\n",
    "        move[(sx, sy, 0)] = 0\n",
    "\n",
    "        while q:\n",
    "            x, y, keys = q.popleft()\n",
    "            _m = move[(x, y, keys)]\n",
    "            _m += 1\n",
    "            \n",
    "            for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:\n",
    "                if 0 <= i < m and 0 <= j < n and grid[i][j] != '#':\n",
    "                    if grid[i][j].isupper() and keys & 1 << (ord(grid[i][j])- ord('A')) == 0:\n",
    "                        continue\n",
    "                    new_key = keys\n",
    "                    if grid[i][j].islower():\n",
    "                        new_key |= 1 << (ord(grid[i][j]) - ord('a'))\n",
    "                        if new_key == (1 << keycnt) - 1:\n",
    "                            return _m\n",
    "\n",
    "                    if (i, j, new_key) not in move:\n",
    "                        q.append((i, j, new_key))\n",
    "                        move[(i, j, new_key)] = _m\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, g: List[str]) -> int:\n",
    "        dirs = [[0,1], [0,-1], [1,0], [-1,0]]\n",
    "        n, m, cnt = len(g), len(g[0]), 0\n",
    "        dist = defaultdict(lambda : 0x3f3f3f3f)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                c = g[i][j]\n",
    "                if c == '@':\n",
    "                    d = deque([(i, j, 0)])\n",
    "                    dist[(i, j, 0)] = 0\n",
    "                elif 'a' <= c <= 'z':\n",
    "                    cnt += 1\n",
    "        while d:\n",
    "            x, y, cur = d.popleft()\n",
    "            step = dist[(x, y, cur)]\n",
    "            for di in dirs:\n",
    "                nx, ny = x + di[0], y + di[1]\n",
    "                if nx < 0 or nx >= n or ny < 0 or ny >= m:\n",
    "                    continue\n",
    "                c = g[nx][ny]\n",
    "                if c == '#':\n",
    "                    continue\n",
    "                if 'A' <= c <= 'Z' and (cur >> (ord(c) - ord('A')) & 1) == 0:\n",
    "                    continue\n",
    "                ncur = cur\n",
    "                if 'a' <= c <= 'z':\n",
    "                    ncur |= (1 << (ord(c) - ord('a')))\n",
    "                if ncur == (1 << cnt) - 1:\n",
    "                    return step + 1\n",
    "                if step + 1 >= dist[(nx, ny, ncur)]:\n",
    "                    continue\n",
    "                dist[(nx, ny, ncur)] = step + 1\n",
    "                d.append((nx, ny, ncur))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        # x, y, cur_keys\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        q = deque()\n",
    "        key_sum = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ch = grid[i][j]\n",
    "                if ch == '@':\n",
    "                    q.append((i, j, 0, 0))\n",
    "                elif ch.islower():\n",
    "                    key_sum ^= (1 << (ord(ch) - ord('a')))\n",
    "        vis = set(q)\n",
    "        d = ((0, 1), (0, -1), (1, 0), (-1, 0))\n",
    "        while q:\n",
    "            x, y, s, step = q.popleft()\n",
    "            if s == key_sum:\n",
    "                return step\n",
    "            for dx, dy in d:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if nx >= 0 and nx < n and ny >= 0 and ny < m and grid[nx][ny] != '#' and (nx, ny, s) not in vis:\n",
    "                    vis.add((nx, ny, s))\n",
    "                    ch = grid[nx][ny]\n",
    "                    # 钥匙\n",
    "                    if ch.islower():\n",
    "                        pos = 1 << (ord(ch)-ord('a'))\n",
    "                        # 已经拿过钥匙\n",
    "                        if s&pos:\n",
    "                            q.append((nx, ny, s, step+1))\n",
    "                        else:\n",
    "                            if s^pos == key_sum:\n",
    "                                return step+1\n",
    "                            q.append((nx, ny, s^pos, step+1))\n",
    "                    # 锁\n",
    "                    elif ch.isupper():\n",
    "                        pos = 1 << (ord(ch)-ord('A'))\n",
    "                        # 有对应钥匙\n",
    "                        if s&pos:\n",
    "                            q.append((nx, ny, s, step+1))\n",
    "                    else:\n",
    "                        q.append((nx, ny, s, step+1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        start_x, start_y = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == \"@\")\n",
    "\n",
    "        k = sum(v.islower() for row in grid for v in row)\n",
    "\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "\n",
    "        # (i, j, state) 用 state 表示找到钥匙的状态\n",
    "        q = deque([(start_x, start_y, 0)])\n",
    "        seen = set([(start_x, start_y, 0)])\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x, y, state = q.popleft()\n",
    "                # 找到所有钥匙\n",
    "                if state == (1<<k) - 1:\n",
    "                    return res\n",
    "\n",
    "                for dx, dy in pairwise(dirs):\n",
    "                    next_x, next_y = x + dx, y + dy\n",
    "                    next_state = state\n",
    "\n",
    "                    if 0 <= next_x < m and 0 <= next_y < n:\n",
    "                        ch = grid[next_x][next_y]\n",
    "\n",
    "                        # 墙 / 锁缺钥匙\n",
    "                        if ch == \"#\" or ch.isupper() and (state & (1 << (ord(ch) - ord(\"A\")))) == 0:\n",
    "                            continue\n",
    "\n",
    "                        # 钥匙\n",
    "                        if ch.islower():\n",
    "                            next_state |= 1 << (ord(ch) - ord(\"a\"))\n",
    "\n",
    "                        # 入队\n",
    "                        if (next_x, next_y, next_state) not in seen:\n",
    "                            seen.add((next_x, next_y, next_state))\n",
    "                            q.append((next_x, next_y, next_state))\n",
    "            res += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        res = -1\n",
    "        visited = set()\n",
    "        key_to_idx = dict()\n",
    "        ex,ey = -1 ,-1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j].islower():\n",
    "                    idx = len(key_to_idx)\n",
    "                    key_to_idx[grid[i][j]] = idx\n",
    "                elif grid[i][j] == \"@\":\n",
    "                     ex,ey = i,j\n",
    "        q = collections.deque([(ex,ey,0)])\n",
    "\n",
    "        visited.add((ex,ey,0))\n",
    "        level = 0\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = collections.deque()\n",
    "            while tmp:\n",
    "                x,y,k = tmp.popleft()\n",
    "                for i,j in ((x,y+1),(x,y-1),(x+1,y),(x-1,y)):\n",
    "                    if 0<=i<m and 0<=j<n:\n",
    "                        if grid[i][j] != '#':\n",
    "                            if grid[i][j] =='.' or grid[i][j] =='@':\n",
    "                                if (i,j,k) not in visited:\n",
    "                                    visited.add((i,j,k))\n",
    "                                    q.append((i,j,k))\n",
    "                            elif grid[i][j].islower():\n",
    "                                kid = key_to_idx[grid[i][j]]\n",
    "                                new_k = k | (1 << kid)\n",
    "\n",
    "                                if new_k == (1 << (len(key_to_idx))) - 1:\n",
    "                                    return level + 1\n",
    "                                if (i,j,new_k) not in visited:\n",
    "                                  visited.add((i,j,new_k))\n",
    "                                  q.append((i,j,new_k))\n",
    "                            elif grid[i][j].isupper():\n",
    "                                lock_k = key_to_idx[grid[i][j].lower()]\n",
    "                                if k & (1<<lock_k) and (i,j,k) not in visited:\n",
    "                                    q.append((i,j,k))\n",
    "                                    visited.add((i,j,k))\n",
    "            level += 1\n",
    "        return -1\n",
    "                                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        #解题思路：\n",
    "        #用一个集合来存储需要收集的钥匙\n",
    "        #用一个集合来存储已经收集了的钥匙\n",
    "        #每一次收集可以移动的位置\n",
    "        #错误，因为不同方向收集钥匙时路径没有加和，为了收集所有的钥匙，要允许走过的路重复走\n",
    "        #解析：\n",
    "        #定义一个队列q来存储当前位置以及当前拥有的钥匙的状态，即 (i,j,state)\n",
    "        #(i,j)表示当前位置\n",
    "        #state表示当前拥有的钥匙的状态,state的第i位为1表示当前拥有第i把钥匙\n",
    "\n",
    "        k = 0 #需要的钥匙数\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        path = []\n",
    "        visited = set()\n",
    "\n",
    "        #需要收集的钥匙\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j].islower():\n",
    "                    k += 1\n",
    "                if grid[i][j] == '@':\n",
    "                    path.append((i,j,0))\n",
    "                    visited.add((i,j,0))\n",
    "\n",
    "        step = 0\n",
    "        while path:\n",
    "            for _ in range(len(path)):\n",
    "                i,j,state = path.pop(0)\n",
    "                if state == (1 << k) - 1:\n",
    "                    return step\n",
    "\n",
    "                for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                    nxt = state\n",
    "                     # 在边界范围内\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        c = grid[x][y]\n",
    "                        # 是墙，或者是锁，但此时没有对应的钥匙，无法通过\n",
    "                        if c == '#' or c.isupper() and (state & (1 << (ord(c) - ord('A')))) == 0:\n",
    "                            continue\n",
    "                        # 是钥匙\n",
    "                        if c.islower():\n",
    "                            # 更新状态\n",
    "                            nxt |= 1 << (ord(c) - ord('a'))\n",
    "                        # 此状态未访问过，入队\n",
    "                        if (x, y, nxt) not in visited:\n",
    "                            visited.add((x, y, nxt))\n",
    "                            path.append((x, y, nxt))\n",
    "            step += 1\n",
    "\n",
    "        return -1     \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx = sy = 0\n",
    "        key_to_idx = dict()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"@\":\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].islower():\n",
    "                    if grid[i][j] not in key_to_idx:\n",
    "                        idx = len(key_to_idx)\n",
    "                        key_to_idx[grid[i][j]] = idx\n",
    "\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        dist = dict()\n",
    "        dist[(sx, sy, 0)] = 0\n",
    "        while q:\n",
    "            x, y, mask = q.popleft()\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != \"#\":\n",
    "                    if grid[nx][ny] == \".\" or grid[nx][ny] == \"@\":\n",
    "                        if (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "                    elif grid[nx][ny].islower():\n",
    "                        idx = key_to_idx[grid[nx][ny]]\n",
    "                        if (nx, ny, mask | (1 << idx)) not in dist:\n",
    "                            dist[(nx, ny, mask | (1 << idx))] = dist[(x, y, mask)] + 1\n",
    "                            if (mask | (1 << idx)) == (1 << len(key_to_idx)) - 1:\n",
    "                                return dist[(nx, ny, mask | (1 << idx))]\n",
    "                            q.append((nx, ny, mask | (1 << idx)))\n",
    "                    else:\n",
    "                        idx = key_to_idx[grid[nx][ny].lower()]\n",
    "                        if (mask & (1 << idx)) and (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        #copy\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        si,sj= next((i,j) for i in range(m) for j in range(n) if grid[i][j] == '@')#if 放在前边就要else吗\n",
    "        k = sum(v.islower() for row in grid for v in row)\n",
    "        dirs = (-1,0,1,0,-1)\n",
    "        q= deque([(si,sj,0)])\n",
    "        vis = {(si,sj,0)}\n",
    "        ans =  0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i,j,state = q.popleft()\n",
    "                if state == (1<<k)-1:\n",
    "                    return ans\n",
    "                for a,b in pairwise(dirs):\n",
    "                    x,y = i+a,j+b\n",
    "                    nxt = state\n",
    "                    if 0<=x<m and 0<=y <n:\n",
    "                        c= grid[x][y]\n",
    "                        if c  == '#' or c.isupper() and (state&(1<<(ord(c)-ord('A')))) ==0:\n",
    "                            continue\n",
    "                        if c.islower():\n",
    "                            nxt |= 1<<(ord(c)-ord('a'))\n",
    "                        if (x,y,nxt) not in vis:\n",
    "                            vis.add((x,y,nxt))\n",
    "                            q.append((x,y,nxt))\n",
    "            ans += 1\n",
    "        return -1          \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx = sy = 0\n",
    "        key_to_idx = dict()\n",
    "        idx=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"@\":\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].islower():\n",
    "                    if grid[i][j] not in key_to_idx:\n",
    "                        key_to_idx[grid[i][j]] = idx\n",
    "                        idx+=1\n",
    "\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        dist = dict()\n",
    "        dist[(sx, sy, 0)] = 0\n",
    "        while q:\n",
    "            x, y, mask = q.popleft()\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != \"#\":\n",
    "                    if grid[nx][ny] == \".\" or grid[nx][ny] == \"@\":\n",
    "                        if (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "                    elif grid[nx][ny].islower():\n",
    "                        idx = key_to_idx[grid[nx][ny]]\n",
    "                        if (nx, ny, mask | (1 << idx)) not in dist:\n",
    "                            dist[(nx, ny, mask | (1 << idx))] = dist[(x, y, mask)] + 1\n",
    "                            if (mask | (1 << idx)) == (1 << len(key_to_idx)) - 1:\n",
    "                                return dist[(nx, ny, mask | (1 << idx))]\n",
    "                            q.append((nx, ny, mask | (1 << idx)))\n",
    "                    else:\n",
    "                        idx = key_to_idx[grid[nx][ny].lower()]\n",
    "                        if (mask & (1 << idx)) and (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx = sy = 0\n",
    "        key_to_idx = dict()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"@\":\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].islower():\n",
    "                    if grid[i][j] not in key_to_idx:\n",
    "                        idx = len(key_to_idx)\n",
    "                        key_to_idx[grid[i][j]] = idx\n",
    "\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        dist = dict()\n",
    "        dist[(sx, sy, 0)] = 0\n",
    "        while q:\n",
    "            x, y, mask = q.popleft()\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != \"#\":\n",
    "                    if grid[nx][ny] == \".\" or grid[nx][ny] == \"@\":\n",
    "                        if (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "                    elif grid[nx][ny].islower():\n",
    "                        idx = key_to_idx[grid[nx][ny]]\n",
    "                        if (nx, ny, mask | (1 << idx)) not in dist:\n",
    "                            dist[(nx, ny, mask | (1 << idx))] = dist[(x, y, mask)] + 1\n",
    "                            if (mask | (1 << idx)) == (1 << len(key_to_idx)) - 1:\n",
    "                                return dist[(nx, ny, mask | (1 << idx))]\n",
    "                            q.append((nx, ny, mask | (1 << idx)))\n",
    "                    else:\n",
    "                        idx = key_to_idx[grid[nx][ny].lower()]\n",
    "                        if (mask & (1 << idx)) and (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx, sy = -1, -1\n",
    "        cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].isalpha():\n",
    "                    cnt += 1\n",
    "        keys = 'abcdef'\n",
    "        suo = 'ABCDEF'\n",
    "        # print(cnt)\n",
    "        cnt = cnt // 2\n",
    "        mask = (1 << cnt) - 1\n",
    "        step = 0\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        vis = {(sx, sy, 0)}\n",
    "        while q:\n",
    "            \n",
    "            for _ in range(len(q)):\n",
    "                x, y, cur = q.popleft()\n",
    "                if cur == mask:\n",
    "                    return step\n",
    "                for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != '#':\n",
    "                        tmp = grid[nx][ny]\n",
    "                        if tmp in keys:\n",
    "                            if (nx, ny, cur | 1 << (ord(tmp) - ord('a'))) not in vis:\n",
    "                                vis.add((nx, ny, cur | 1 << (ord(tmp) - ord('a'))))\n",
    "                                q.append((nx, ny, cur | 1 << (ord(tmp) - ord('a'))))\n",
    "                        elif tmp in suo:\n",
    "                            need = 1 << (ord(tmp) - ord('A'))\n",
    "                            if cur & need:\n",
    "                                if (nx, ny, cur) not in vis:\n",
    "                                    vis.add((nx, ny, cur))\n",
    "                                    q.append((nx, ny, cur))\n",
    "                        else:\n",
    "                            if (nx, ny, cur) not in vis:\n",
    "                                vis.add((nx, ny, cur))\n",
    "                                q.append((nx, ny, cur))\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "                m,n = len(grid), len(grid[0])\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        if grid[i][j]=='@':\n",
    "                            si = i\n",
    "                            sj = j\n",
    "                k = sum(v.islower() for row in grid for v in row)\n",
    "                dirs = (-1,0,1,0,-1)\n",
    "                q = deque([(si,sj,0)])\n",
    "                vis = {(si,sj,0)}\n",
    "                ans = 0\n",
    "                while q:\n",
    "                    for _ in range(len(q)):\n",
    "                        i,j,state = q.popleft()\n",
    "                        if state == (1<<k)-1:\n",
    "                            return ans\n",
    "                        for a,b in pairwise(dirs):\n",
    "                            x,y = i+a, j+b\n",
    "                            nxt = state\n",
    "                            if 0<=x<m and 0<=y<n:\n",
    "                                c = grid[x][y]\n",
    "                                if c=='#' or c.isupper() and (state & (1<<(ord(c)-ord('A'))))==0:\n",
    "                                    continue\n",
    "                                if c.islower():\n",
    "                                    nxt |=1<<(ord(c)-ord('a'))\n",
    "                                if (x,y,nxt) not in vis:\n",
    "                                    vis.add((x,y,nxt))\n",
    "                                    q.append((x,y,nxt))\n",
    "                    ans+=1\n",
    "                return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx = sy = 0\n",
    "        key_to_idx = dict()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"@\":\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].islower():\n",
    "                    if grid[i][j] not in key_to_idx:\n",
    "                        idx = len(key_to_idx)\n",
    "                        key_to_idx[grid[i][j]] = idx\n",
    "\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        dist = dict()\n",
    "        dist[(sx, sy, 0)] = 0\n",
    "        while q:\n",
    "            x, y, mask = q.popleft()\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != \"#\":\n",
    "                    if grid[nx][ny] == \".\" or grid[nx][ny] == \"@\":\n",
    "                        if (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "                    elif grid[nx][ny].islower():\n",
    "                        idx = key_to_idx[grid[nx][ny]]\n",
    "                        if (nx, ny, mask | (1 << idx)) not in dist:\n",
    "                            dist[(nx, ny, mask | (1 << idx))] = dist[(x, y, mask)] + 1\n",
    "                            if (mask | (1 << idx)) == (1 << len(key_to_idx)) - 1:\n",
    "                                return dist[(nx, ny, mask | (1 << idx))]\n",
    "                            q.append((nx, ny, mask | (1 << idx)))\n",
    "                    else:\n",
    "                        idx = key_to_idx[grid[nx][ny].lower()]\n",
    "                        if (mask & (1 << idx)) and (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "import heapq\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\r\n",
    "        \"\"\"使用 BFS\r\n",
    "\r\n",
    "        1. 找到起点和钥匙\r\n",
    "        2. 使用 BFS 搜索\r\n",
    "        3. 记录已经访问过的状态\r\n",
    "        4. 优化：使用位运算记录状态\r\n",
    "        5. 优化：使用最小堆记录状态\r\n",
    "\r\n",
    "        测试用例：\r\n",
    "        ```\r\n",
    "        [\"@.a.#\",\"###.#\",\"b.A.B\"]\\n[\"@..aA\",\"..B#.\",\"....b\"]\\n[\"@Aa\"]\r\n",
    "        [\"@...a\",\".###A\",\"b.BCc\"]\r\n",
    "        ```\r\n",
    "        \"\"\"\r\n",
    "\r\n",
    "        # 1. 找到起点和钥匙\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        start: tuple[int, int] | None = None\r\n",
    "        keys = 0\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == '@':  # 起点\r\n",
    "                    start = (i, j)\r\n",
    "                elif 'a' <= grid[i][j] <= 'f':\r\n",
    "                    keys |= (1 << (ord(grid[i][j]) - ord('a')))\r\n",
    "        if start is None:  # 没有起点\r\n",
    "            return -1\r\n",
    "        # 2. 使用 BFS 搜索\r\n",
    "        queue = [(int(0), start[0], start[1], int(0))]\r\n",
    "        visited = set()\r\n",
    "        while queue:\r\n",
    "            steps, x, y, state = heapq.heappop(queue)\r\n",
    "            if state == keys:  # 已经找到所有钥匙\r\n",
    "                return steps\r\n",
    "            if (x, y, state) in visited:  # 已经访问过\r\n",
    "                continue\r\n",
    "            visited.add((x, y, state))  # 记录已经访问过的状态\r\n",
    "            for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):  # 遍历四个方向\r\n",
    "                nx, ny = x + dx, y + dy\r\n",
    "                if not (0 <= nx < m and 0 <= ny < n):  # 越界\r\n",
    "                    continue\r\n",
    "                if grid[nx][ny] == '#':  # 遇到墙\r\n",
    "                    continue\r\n",
    "                if 'A' <= grid[nx][ny] <= 'F' and not state & (1 << (ord(grid[nx][ny]) - ord('A'))):\r\n",
    "                    # 遇到锁，但是没有对应的钥匙\r\n",
    "                    continue\r\n",
    "                if 'a' <= grid[nx][ny] <= 'f':  # 遇到钥匙\r\n",
    "                    nstate = state | (1 << (ord(grid[nx][ny]) - ord('a')))\r\n",
    "                else:  # 没有遇到钥匙\r\n",
    "                    nstate = state\r\n",
    "                heapq.heappush(queue, (steps + 1, nx, ny, nstate))\r\n",
    "        return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        sx = sy = 0\n",
    "        key_to_idx = dict()\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"@\":\n",
    "                    sx, sy = i, j\n",
    "                elif grid[i][j].islower():\n",
    "                    if grid[i][j] not in key_to_idx:\n",
    "                        idx = len(key_to_idx)\n",
    "                        key_to_idx[grid[i][j]] = idx\n",
    "\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        dist = dict()\n",
    "        dist[(sx, sy, 0)] = 0\n",
    "        while q:\n",
    "            x, y, mask = q.popleft()\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != \"#\":\n",
    "                    if grid[nx][ny] == \".\" or grid[nx][ny] == \"@\":\n",
    "                        if (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "                    elif grid[nx][ny].islower():\n",
    "                        idx = key_to_idx[grid[nx][ny]]\n",
    "                        if (nx, ny, mask | (1 << idx)) not in dist:\n",
    "                            dist[(nx, ny, mask | (1 << idx))] = dist[(x, y, mask)] + 1\n",
    "                            if (mask | (1 << idx)) == (1 << len(key_to_idx)) - 1:\n",
    "                                return dist[(nx, ny, mask | (1 << idx))]\n",
    "                            q.append((nx, ny, mask | (1 << idx)))\n",
    "                    else:\n",
    "                        idx = key_to_idx[grid[nx][ny].lower()]\n",
    "                        if (mask & (1 << idx)) and (nx, ny, mask) not in dist:\n",
    "                            dist[(nx, ny, mask)] = dist[(x, y, mask)] + 1\n",
    "                            q.append((nx, ny, mask))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        #find start pos(si, sj)\n",
    "        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # count key number\n",
    "        k = sum(v.islower() for row in grid for v in row)\n",
    "\n",
    "        #dirs = (-1, 0, 1, 0, -1)\n",
    "        dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))\n",
    "        q = collections.deque([(si, sj, 0)])\n",
    "\n",
    "        vis = {(si, sj, 0)}\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j, state = q.popleft()\n",
    "                #find all key, return bushu\n",
    "                if state == (1 << k) - 1:\n",
    "                    return ans\n",
    "                \n",
    "                # find four dic\n",
    "                for a, b  in dirs:\n",
    "                    x, y = i + a, j + b\n",
    "                    nxt = state\n",
    "\n",
    "                    # in range\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        c = grid[x][y]\n",
    "                        #print(grid)\n",
    "                        #print(c)\n",
    "                        \n",
    "                        if c == '#' or c.isupper() and (state & (1 << (ord(c) - ord('A')))) == 0:\n",
    "                            #if c != '#':\n",
    "                                #res = (1 << (ord(c) - ord('A')))\n",
    "                                #print(\"res=\" + str(res))\n",
    "                            continue\n",
    "                        # is key\n",
    "                        if c.islower():\n",
    "                            #update state\n",
    "                            nxt |= 1 << (ord(c) - ord('a'))\n",
    "                        # not reach, pushc\n",
    "                        if (x , y, nxt) not in vis:\n",
    "                            vis.add((x, y, nxt))\n",
    "                            q.append((x, y, nxt))\n",
    "            # ans add 1\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        si,sj  = next( (i,j) for i in range(m) for j in range(n) if grid[i][j]=='@')\n",
    "        k = sum(v.islower() for row in grid for v in row)\n",
    "        dirs = (-1,0,1,0,-1)\n",
    "        q = deque([(si,sj,0)])\n",
    "        vis = {(si,sj,0)}\n",
    "        ans = 0 \n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i,j,state = q.popleft()\n",
    "                if state ==(1<<k) -1: return ans \n",
    "                for a,b in pairwise(dirs):\n",
    "                    x,y = i+a,j+b \n",
    "                    nxt = state \n",
    "                    if 0<=x<m and 0<=y<n:\n",
    "                        c = grid[x][y]\n",
    "                        if c=='#' or c.isupper() and (state & 1<<(ord(c)-ord('A'))) ==0:\n",
    "                            continue \n",
    "                        if c.islower():\n",
    "                            nxt = nxt | 1<<(ord(c)-ord('a')) \n",
    "                        if (x,y,nxt) not in vis:\n",
    "                            vis.add((x,y,nxt))\n",
    "                            q.append((x,y,nxt))\n",
    "            ans+=1\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        start = None\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        \n",
    "        keys = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    start = (i,j)\n",
    "                if grid[i][j].isalpha() and grid[i][j].islower():\n",
    "                    keys.add(grid[i][j])\n",
    "        \n",
    "        hashmap = defaultdict(int)\n",
    "        for i , key in enumerate(list(keys)):\n",
    "            hashmap[key] = i\n",
    "\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "\n",
    "        step = 0\n",
    "        queue = deque([(start[0],start[1],0)])\n",
    "        target = 2 ** len(keys) - 1\n",
    "        visited = set()\n",
    "\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                i , j ,state = queue.popleft()\n",
    "                if state == target:return step\n",
    "                for di , dj in direction:\n",
    "                    ni , nj = i + di , j + dj\n",
    "                    if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != '#':\n",
    "                        if grid[ni][nj].isalpha():\n",
    "                            if grid[ni][nj].islower():\n",
    "                                new_state = state | (1 << hashmap[grid[ni][nj]])\n",
    "                                if (ni,nj,new_state) not in visited:\n",
    "                                    visited.add((ni,nj,new_state))\n",
    "                                    queue.append((ni,nj,new_state))\n",
    "                            else:\n",
    "                                if state & (1 << hashmap[grid[ni][nj].lower()]) and (ni,nj,state) not in visited:\n",
    "                                    visited.add((ni,nj,state))\n",
    "                                    queue.append((ni,nj,state))\n",
    "                        else:\n",
    "                            if (ni,nj,state) not in visited:\n",
    "                                visited.add((ni,nj,state))\n",
    "                                queue.append((ni,nj,state))\n",
    "            step += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        queue = collections.deque()\n",
    "        visit = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    queue.append([i, j, 0, 0])\n",
    "                    visit.add((i, j, 0))\n",
    "                if grid[i][j].islower():\n",
    "                    cnt += 1 \n",
    "        target = (1 << cnt) - 1\n",
    "        while queue:\n",
    "            i, j, step, mask = queue.popleft()\n",
    "            if mask == target:\n",
    "                return step\n",
    "            for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] != '#':\n",
    "                    new = mask\n",
    "                    if grid[x][y].islower():\n",
    "                        val = ord(grid[x][y]) - ord('a')\n",
    "                        new |= 1 << val  \n",
    "                    if grid[x][y].isupper():\n",
    "                        val = ord(grid[x][y]) - ord('A')\n",
    "                        if not new & 1 << val:\n",
    "                            continue\n",
    "                    if (x, y, new) in visit:\n",
    "                        continue \n",
    "                    visit.add((x, y, new))\n",
    "                    queue.append([x, y, step + 1, new])\n",
    "        return - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\r\n",
    "        key_idx={}\r\n",
    "        sr,sc=-1,-1\r\n",
    "        R,C=len(grid),len(grid[0])\r\n",
    "        for r in range(R):\r\n",
    "            for c in range(C):\r\n",
    "                if grid[r][c]=='@':\r\n",
    "                    sr,sc=r,c\r\n",
    "                elif grid[r][c].islower():\r\n",
    "                    if grid[r][c] not in key_idx:\r\n",
    "                        key_idx[grid[r][c]]=len(key_idx)\r\n",
    "\r\n",
    "        q=deque([(sr,sc,0)])\r\n",
    "        dis={q[0]:0}\r\n",
    "        target=(1<<(len(key_idx)))-1\r\n",
    "        while q:\r\n",
    "            r,c,mask=q.popleft()\r\n",
    "            step=dis[(r,c,mask)]\r\n",
    "            dirs=[-1,0,1,0,-1]\r\n",
    "            for i in range(4):\r\n",
    "                nr,nc=r+dirs[i],c+dirs[i+1]\r\n",
    "                if nr<0 or nr==R or nc<0 or nc==C:\r\n",
    "                    continue\r\n",
    "                char=grid[nr][nc]\r\n",
    "                if char=='#':\r\n",
    "                    continue\r\n",
    "                elif char.islower():\r\n",
    "                    idx=key_idx[char]\r\n",
    "                    nmask=mask|(1<<idx)\r\n",
    "                    if nmask==target:\r\n",
    "                        return step+1\r\n",
    "                    if (nr,nc,nmask) in dis:\r\n",
    "                        continue\r\n",
    "                    dis[(nr,nc,nmask)]=step+1\r\n",
    "                    q.append((nr,nc,nmask))\r\n",
    "                elif char.isupper():\r\n",
    "                    idx=key_idx[char.lower()]\r\n",
    "                    if mask & (1<<idx)==0 or (nr,nc,mask) in dis:\r\n",
    "                        continue\r\n",
    "                    dis[(nr,nc,mask)]=step+1\r\n",
    "                    q.append((nr,nc,mask))\r\n",
    "                else:\r\n",
    "                    if (nr,nc,mask) in dis:\r\n",
    "                        continue\r\n",
    "                    dis[(nr,nc,mask)]=step+1\r\n",
    "                    q.append((nr,nc,mask))\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        move = [-1,0,1,0,-1]\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        key=0\n",
    "        q = []\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '@':\n",
    "                    q.append((i,j,0))\n",
    "                    vis.add((i,j,0))\n",
    "                if 97<=ord(grid[i][j])<=122:\n",
    "                    key += 1\n",
    "        key = 2**key-1\n",
    "        step = 1\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for x,y,k in q:\n",
    "                for i in range(4):\n",
    "                    xx = x+move[i]\n",
    "                    yy = y+move[i+1]\n",
    "                    if 0<=xx<n and 0<=yy<m and grid[xx][yy] != '#':\n",
    "                        if 65<=ord(grid[xx][yy])<=90 and k&(1<<(ord(grid[xx][yy])-65)) == 0:\n",
    "                            continue\n",
    "                        kk = k|(1<<(ord(grid[xx][yy])-97)) if 97<=ord(grid[xx][yy])<=122 else k\n",
    "                        if kk==key:\n",
    "                            return step\n",
    "                        if (xx,yy,kk) not in vis:\n",
    "                            tmp.append((xx,yy,kk))\n",
    "                            vis.add((xx,yy,kk))\n",
    "            q = tmp\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 找起点 (si, sj)\n",
    "        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "        # 统计钥匙数量\n",
    "        k = sum(v.islower() for row in grid for v in row)\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(si, sj, 0)])\n",
    "        vis = {(si, sj, 0)}\n",
    "        ans = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j, state = q.popleft()\n",
    "                # 找到所有钥匙，返回当前步数\n",
    "                if state == (1 << k) - 1:\n",
    "                    return ans\n",
    "\n",
    "                # 往四个方向搜索\n",
    "                for a, b in pairwise(dirs):\n",
    "                    x, y = i + a, j + b\n",
    "                    nxt = state\n",
    "                    # 在边界范围内\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        c = grid[x][y]\n",
    "                        # 是墙，或者是锁，但此时没有对应的钥匙，无法通过\n",
    "                        if c == '#' or c.isupper() and (state & (1 << (ord(c) - ord('A')))) == 0:\n",
    "                            continue\n",
    "                        # 是钥匙\n",
    "                        if c.islower():\n",
    "                            # 更新状态\n",
    "                            nxt |= 1 << (ord(c) - ord('a'))\n",
    "                        # 此状态未访问过，入队\n",
    "                        if (x, y, nxt) not in vis:\n",
    "                            vis.add((x, y, nxt))\n",
    "                            q.append((x, y, nxt))\n",
    "            # 步数加一\n",
    "            ans += 1\n",
    "        return -1\n",
    "\n",
    "# 作者：ylb\n",
    "# 链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys/solutions/1960449/by-lcbin-mk6o/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dirs = [(0,1),(0,-1),(-1,0),(1,0)]\n",
    "        arr = []\n",
    "        start,k = None,0\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,x in enumerate(row):\n",
    "                if x == '@':\n",
    "                    start = [i,j]\n",
    "                if 'a' <= x <= 'z':\n",
    "                    arr.append(x)\n",
    "                    k += 1\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        d = {e:i for i,e in enumerate(arr)}\n",
    "        mask = (1 << k) - 1\n",
    "        q = deque()\n",
    "        q.append((start[0],start[1],mask))\n",
    "        step = 0\n",
    "        visit = set()\n",
    "        visit.add((start[0],start[1],mask))\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x,y,v = q.popleft()\n",
    "                if v == 0:\n",
    "                    #print(step)\n",
    "                    return step\n",
    "                for dx,dy in dirs:\n",
    "                    nx,ny = x + dx,y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != '#':\n",
    "                        if 'A' <= grid[nx][ny] <= 'Z' and ((v >> d[grid[nx][ny].lower()]) & 1):\n",
    "                            continue\n",
    "                        elif 'a' <= grid[nx][ny] <= 'z':\n",
    "                            v1 = v ^ (1 << d[grid[nx][ny]]) if v >> d[grid[nx][ny]] & 1 else v\n",
    "                            if (nx,ny,v1) not in visit:\n",
    "                                q.append((nx,ny,v1))\n",
    "                                visit.add((nx,ny,v1))\n",
    "                        else:\n",
    "                            if (nx,ny,v) not in visit:\n",
    "                                q.append((nx,ny,v))       \n",
    "                                visit.add((nx,ny,v))  \n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 找起点 (si, sj)\n",
    "        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "        # 统计钥匙数量\n",
    "        k = sum(v.islower() for row in grid for v in row)\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        q = deque([(si, sj, 0)])\n",
    "        vis = {(si, sj, 0)}\n",
    "        ans = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j, state = q.popleft()\n",
    "                # 找到所有钥匙，返回当前步数\n",
    "                if state == (1 << k) - 1:\n",
    "                    return ans\n",
    "\n",
    "                # 往四个方向搜索\n",
    "                for a, b in pairwise(dirs):\n",
    "                    x, y = i + a, j + b\n",
    "                    nxt = state\n",
    "                    # 在边界范围内\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        c = grid[x][y]\n",
    "                        # 是墙，或者是锁，但此时没有对应的钥匙，无法通过\n",
    "                        if c == '#' or c.isupper() and (state & (1 << (ord(c) - ord('A')))) == 0:\n",
    "                            continue\n",
    "                        # 是钥匙\n",
    "                        if c.islower():\n",
    "                            # 更新状态\n",
    "                            nxt |= 1 << (ord(c) - ord('a'))\n",
    "                        # 此状态未访问过，入队\n",
    "                        if (x, y, nxt) not in vis:\n",
    "                            vis.add((x, y, nxt))\n",
    "                            q.append((x, y, nxt))\n",
    "            # 步数加一\n",
    "            ans += 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        queue = collections.deque()\n",
    "        visit = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    queue.append([i, j, 0, 0])\n",
    "                    visit.add((i, j, 0))\n",
    "                if grid[i][j].islower():\n",
    "                    cnt += 1 \n",
    "        target = (1 << cnt) - 1\n",
    "        while queue:\n",
    "            i, j, step, mask = queue.popleft()\n",
    "            if mask == target:\n",
    "                return step\n",
    "            for d in ((-1, 0), (0, -1), (1, 0), (0, 1)):\n",
    "                x = i + d[0]\n",
    "                y = j + d[1]\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] != '#':\n",
    "                    new = mask\n",
    "                    if grid[x][y].islower():\n",
    "                        val = ord(grid[x][y]) - ord('a')\n",
    "                        new |= 1 << val  \n",
    "                    if grid[x][y].isupper():\n",
    "                        val = ord(grid[x][y]) - ord('A')\n",
    "                        if not new & 1 << val:\n",
    "                            continue\n",
    "                    if (x, y, new) in visit:\n",
    "                        continue \n",
    "                    visit.add((x, y, new))\n",
    "                    queue.append([x, y, step + 1, new])\n",
    "        return - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == \"@\":\n",
    "                    si, sj = i, j\n",
    "                    break\n",
    "\n",
    "        k = sum(v.islower() for row in grid for v in row)\n",
    "        directions = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        q = deque([(si, sj, 0)])\n",
    "        vis = {(si, sj, 0)}\n",
    "        ans = 0\n",
    "\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j, state = q.popleft()\n",
    "                if state == (1 << k) - 1:\n",
    "                    return ans\n",
    "\n",
    "                for dx, dy in directions:\n",
    "                    x, y = i + dx, j + dy \n",
    "                    nxt = state\n",
    "                    if 0 <= x < m and 0 <= y < n:\n",
    "                        c = grid[x][y]\n",
    "                        if c == \"#\" or c.isupper() and (state & (1 << (ord(c)-ord('A')))) == 0:\n",
    "                            continue\n",
    "                        if c.islower():\n",
    "                            nxt |= 1 << (ord(c) - ord(\"a\"))\n",
    "                        if (x, y, nxt) not in vis:\n",
    "                            vis.add((x, y, nxt))\n",
    "                            q.append((x, y, nxt))\n",
    "            ans += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        vis=set()\n",
    "        t=0\n",
    "        direc = [(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]=='@':\n",
    "                    begin = (i,j)\n",
    "                    \n",
    "                if grid[i][j].islower():\n",
    "                    # keys[grid[i][j]]=t  #小写，钥匙\n",
    "                    t+=1\n",
    "\n",
    "        # +ord('A')-ord('a')\n",
    "\n",
    "        keystate = 0\n",
    "\n",
    "        \n",
    "        quene = collections.deque()\n",
    "        quene.append((begin[0],begin[1],keystate,0))\n",
    "        vis.add((begin[0],begin[1],keystate))\n",
    "\n",
    "\n",
    "        while quene:\n",
    "            i,j,keystate,step = quene.popleft()\n",
    "\n",
    "            if keystate == 2**t -1 :\n",
    "                return step\n",
    "            for dx,dy in direc:\n",
    "                x=i+dx\n",
    "                y=j+dy\n",
    "                keystate2 = keystate\n",
    "                if 0<=x<m and 0<=y<n and (x,y,keystate) not in vis and grid[x][y]!='#':\n",
    "                    if grid[x][y].isupper() and keystate & 1 << (ord(grid[x][y])-ord('A')) == 0:\n",
    "                        continue\n",
    "                    if grid[x][y].islower():\n",
    "                        keystate2 |= 1 << (ord(grid[x][y])-ord('a'))\n",
    "                    quene.append((x,y,keystate2,step+1))\n",
    "\n",
    "                    vis.add((x,y,keystate))\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        # range\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "\n",
    "        # find start\n",
    "        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # dirs \n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        locks = ['A', 'B', 'C', 'D', 'E', 'F']\n",
    "        lock2pos = {key_let: i for i, key_let in enumerate(locks)}\n",
    "        key2pos = {key_let.lower(): i for i, key_let in enumerate(locks)}\n",
    "        total_num_keys = sum(grid[i][j].islower() for i in range(m) for j in range(n))\n",
    "        key_checker = '0'*total_num_keys\n",
    "\n",
    "        q = deque()\n",
    "        q.append((si, sj, key_checker))\n",
    "\n",
    "        visited = set()\n",
    "        visited.add((si, sj, key_checker))\n",
    "        res = 0\n",
    "\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j, state = q.popleft()\n",
    "\n",
    "                # break condition\n",
    "                if state == '1'*total_num_keys:\n",
    "                    return res\n",
    "                # search\n",
    "                for a, b in pairwise(dirs):\n",
    "                    ni, nj, nstate = i+a, j+b, state\n",
    "                    if 0<=ni<m and 0<=nj<n: # works only with valid map\n",
    "\n",
    "                        # hit wall or hit lock but no key\n",
    "                        if grid[ni][nj] == \"#\" or (grid[ni][nj].isupper() and state[lock2pos[grid[ni][nj]]] == '0'):\n",
    "                            continue\n",
    "\n",
    "\n",
    "                        # hit key and update states\n",
    "                        if grid[ni][nj].islower():\n",
    "                            tmp = list(nstate)\n",
    "                            tmp[key2pos[grid[ni][nj]]] = '1'\n",
    "                            nstate = ''.join(tmp)\n",
    "\n",
    "\n",
    "                        # if ( i,j, current state) is not visited \n",
    "                        if (ni, nj, nstate) not in visited:\n",
    "                            visited.add((ni, nj, nstate))\n",
    "                            q.append((ni, nj, nstate))\n",
    "            res += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # # range\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        \n",
    "\n",
    "        # # find start\n",
    "        # si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # # dirs \n",
    "        # dirs = (-1, 0, 1, 0, -1)\n",
    "\n",
    "        # # nkeys\n",
    "        # nkeys = sum(grid[i][j].islower() for i in range(m) for j in range(n))\n",
    "\n",
    "        # # state\n",
    "        # visited = set()\n",
    "        # visited.add((si, sj, '0'*nkeys)) # we use 0 to indicate it's not visited, we use 1 to indicate visited and already grabed the key\n",
    "\n",
    "        # # queue\n",
    "        # q = deque()\n",
    "        # q.append((si, sj, '0'*nkeys)) # here is the state and the above is the visited \n",
    "\n",
    "\n",
    "        # keys = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "        # check = {key: i for i, key in enumerate(keys)}\n",
    "\n",
    "        # out = 0\n",
    "        # while q:\n",
    "        #     for _ in range(len(q)): #We need to fninish all directions in a layer\n",
    "        #         i, j, state = q.popleft()\n",
    "        #         # break condition (final and invalid)\n",
    "        #         if state == '1'*nkeys:\n",
    "        #             return out\n",
    "\n",
    "        #         for a, b in pairwise(dirs):\n",
    "        #             ni, nj = i+a, j+b\n",
    "        #             nstate = state # this is important as we usually don't want to mess up with the previous state\n",
    "\n",
    "        #             # wihtin range\n",
    "        #             if 0<=ni<m and 0<=nj<n:\n",
    "        #                 # if not satisfied (1. hit wall, meet lock and no currresponding key)\n",
    "        #                 if grid[ni][nj] == '#' or (grid[ni][nj].isupper() and nstate[check[grid[ni][nj].lower()]] == '0'):\n",
    "        #                     continue\n",
    "\n",
    "\n",
    "        #                 # if satisfied, update state: pickup the key\n",
    "        #                 if grid[ni][nj].islower():\n",
    "        #                     # print(check[grid[ni][nj].lower()])\n",
    "        #                     tmp = list(nstate)\n",
    "        #                     tmp[check[grid[ni][nj].lower()]] = '1'\n",
    "        #                     nstate = ''.join(tmp)\n",
    "        #                     # pass\n",
    "\n",
    "\n",
    "        #                 # register new visits and queue\n",
    "        #                 if (ni, nj, nstate) not in visited:\n",
    "        #                     q.append((ni, nj, nstate))\n",
    "        #                     visited.add((ni, nj, nstate))\n",
    "\n",
    "        #     out += 1\n",
    "\n",
    "        # return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # # size\n",
    "        # m = len(grid)\n",
    "        # n = len(grid[0])\n",
    "\n",
    "\n",
    "        # # find start\n",
    "        # si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # #set buffer\n",
    "        # key_tot = sum(v.islower() for row in grid for v in row)\n",
    "        # all_pos = ['A', 'B', 'C', 'D', 'E', 'F']\n",
    "        # key_in_consider = all_pos[:key_tot]\n",
    "        # # lock2idx\n",
    "        # lock2idx = {cur: i for i, cur in enumerate(key_in_consider)}\n",
    "        # all_pos = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "        # key_in_consider = all_pos[:key_tot]\n",
    "        # key2idx = {cur: i for i, cur in enumerate(key_in_consider)}\n",
    "        \n",
    "        # keys = '0' * key_tot # == 1 for has this key == 0 for not having this key\n",
    "        # vis = {(si, sj, keys)} # location i, location j, key status (initially no keys obtained)\n",
    "        # # this is different as not only the location but also the status of the keys need to be registered \n",
    "        # step = 0 # final output\n",
    "\n",
    "        # dirs = (-1, 0, 1, 0, -1) # all possible directions (dirs[i], dirs[i+1]) for i in range(4)\n",
    "        # q = deque([(si, sj, keys)])\n",
    "\n",
    "        # while q:\n",
    "        #     for _ in range(len(q)): # needs to consider the shortest path so each layer is counted only once            \n",
    "\n",
    "        #         i, j, state = q.popleft()\n",
    "        #         # print(state)\n",
    "        #         if state == '1'*key_tot: # output condition\n",
    "        #             return step\n",
    "                \n",
    "        #         for a, b in pairwise(dirs):\n",
    "        #             ni, nj = i + a, j + b\n",
    "        #             nstate = state\n",
    "        #             # now decide if the new location and state are valid\n",
    "\n",
    "        #             # only consider the case when the steps are in the grid\n",
    "        #             if 0 <= ni < m and 0 <= nj < n:\n",
    "        #                 check_pos = grid[ni][nj]\n",
    "        #                 # 1. if is wall or is lock but no key, continue, no count\n",
    "        #                 if check_pos == '#' or (check_pos.isupper() and nstate[lock2idx[check_pos]] == '0'):\n",
    "        #                     continue\n",
    "\n",
    "\n",
    "        #                 # 2. if key, update state,\n",
    "        #                 if check_pos.islower():\n",
    "        #                     list_state = list(nstate)\n",
    "        #                     list_state[key2idx[check_pos]] = '1'\n",
    "        #                     nstate = ''.join(list_state)\n",
    "        #                     # print(nstate)\n",
    "                        \n",
    "\n",
    "\n",
    "        #                 # 3. if not visited, add to vis and add to q\n",
    "        #                 if (ni, nj, nstate) not in vis:\n",
    "        #                     vis.add((ni, nj, nstate))\n",
    "        #                     q.append((ni, nj, nstate))\n",
    "        #     # complete one layer\n",
    "        #     step += 1\n",
    "\n",
    "        # return -1 \n",
    "\n",
    "                    \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "\n",
    "        r, c = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        si,sj = -1, -1\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if grid[i][j] == '@':\n",
    "                    si, sj = i, j\n",
    "                elif 'a' <= grid[i][j] < 'z':\n",
    "                    cnt += 1\n",
    "\n",
    "        queue = collections.deque([(si, sj, 0, 0)])\n",
    "        seen = set()\n",
    "        seen.add((si, sj, 0))\n",
    "\n",
    "        while queue:\n",
    "            ii, jj, state, step = queue.popleft()\n",
    "            if state == (1 << cnt) - 1:\n",
    "                return step\n",
    "\n",
    "            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                newi, newj = ii + di, jj + dj\n",
    "\n",
    "                if 0 <= newi < r and 0 <= newj < c:\n",
    "                    if grid[newi][newj] == '#':\n",
    "                        continue\n",
    "                    if grid[newi][newj] in '.@':\n",
    "                        if (newi, newj, state) not in seen:\n",
    "                            queue.append((newi, newj, state, step + 1))\n",
    "                            seen.add((newi, newj, state))\n",
    "                    elif 'a' <= grid[newi][newj] <= 'z':\n",
    "                        mask = 1 << (ord(grid[newi][newj]) - 97)\n",
    "                        if (newi, newj, state | mask) not in seen:\n",
    "                            queue.append((newi, newj, state | mask, step + 1))\n",
    "                            seen.add((newi, newj, state | mask))\n",
    "                    else:\n",
    "                        mask = 1 << (ord(grid[newi][newj]) - 65)\n",
    "                        if mask & state:\n",
    "                            if (newi, newj, state) not in seen:\n",
    "                                queue.append((newi, newj, state, step + 1))\n",
    "                                seen.add((newi, newj, state))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        \n",
    "        # range\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "\n",
    "        # find start\n",
    "        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # dirs \n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "\n",
    "        # nkeys\n",
    "        nkeys = sum(grid[i][j].islower() for i in range(m) for j in range(n))\n",
    "\n",
    "        # state\n",
    "        visited = set()\n",
    "        visited.add((si, sj, '0'*nkeys)) # we use 0 to indicate it's not visited, we use 1 to indicate visited and already grabed the key\n",
    "\n",
    "        # queue\n",
    "        q = deque()\n",
    "        q.append((si, sj, '0'*nkeys)) # here is the state and the above is the visited \n",
    "\n",
    "\n",
    "        keys = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "        check = {key: i for i, key in enumerate(keys)}\n",
    "\n",
    "        out = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)): #We need to fninish all directions in a layer\n",
    "                i, j, state = q.popleft()\n",
    "                # break condition (final and invalid)\n",
    "                if state == '1'*nkeys:\n",
    "                    return out\n",
    "\n",
    "                for a, b in pairwise(dirs):\n",
    "                    ni, nj = i+a, j+b\n",
    "                    nstate = state # this is important as we usually don't want to mess up with the previous state\n",
    "\n",
    "                    # wihtin range\n",
    "                    if 0<=ni<m and 0<=nj<n:\n",
    "                        # if not satisfied (1. hit wall, meet lock and no currresponding key)\n",
    "                        if grid[ni][nj] == '#' or (grid[ni][nj].isupper() and nstate[check[grid[ni][nj].lower()]] == '0'):\n",
    "                            continue\n",
    "\n",
    "\n",
    "                        # if satisfied, update state: pickup the key\n",
    "                        if grid[ni][nj].islower():\n",
    "                            # print(check[grid[ni][nj].lower()])\n",
    "                            tmp = list(nstate)\n",
    "                            tmp[check[grid[ni][nj].lower()]] = '1'\n",
    "                            nstate = ''.join(tmp)\n",
    "                            # pass\n",
    "\n",
    "\n",
    "                        # register new visits and queue\n",
    "                        if (ni, nj, nstate) not in visited:\n",
    "                            q.append((ni, nj, nstate))\n",
    "                            visited.add((ni, nj, nstate))\n",
    "\n",
    "            out += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # size\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "\n",
    "        # find start\n",
    "        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        #set buffer\n",
    "        key_tot = sum(v.islower() for row in grid for v in row)\n",
    "        all_pos = ['A', 'B', 'C', 'D', 'E', 'F']\n",
    "        key_in_consider = all_pos[:key_tot]\n",
    "        # lock2idx\n",
    "        lock2idx = {cur: i for i, cur in enumerate(key_in_consider)}\n",
    "        all_pos = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "        key_in_consider = all_pos[:key_tot]\n",
    "        key2idx = {cur: i for i, cur in enumerate(key_in_consider)}\n",
    "        \n",
    "        keys = '0' * key_tot # == 1 for has this key == 0 for not having this key\n",
    "        vis = {(si, sj, keys)} # location i, location j, key status (initially no keys obtained)\n",
    "        # this is different as not only the location but also the status of the keys need to be registered \n",
    "        step = 0 # final output\n",
    "\n",
    "        dirs = (-1, 0, 1, 0, -1) # all possible directions (dirs[i], dirs[i+1]) for i in range(4)\n",
    "        q = deque([(si, sj, keys)])\n",
    "\n",
    "        while q:\n",
    "            for _ in range(len(q)): # needs to consider the shortest path so each layer is counted only once            \n",
    "\n",
    "                i, j, state = q.popleft()\n",
    "                # print(state)\n",
    "                if state == '1'*key_tot: # output condition\n",
    "                    return step\n",
    "                \n",
    "                for a, b in pairwise(dirs):\n",
    "                    ni, nj = i + a, j + b\n",
    "                    nstate = state\n",
    "                    # now decide if the new location and state are valid\n",
    "\n",
    "                    # only consider the case when the steps are in the grid\n",
    "                    if 0 <= ni < m and 0 <= nj < n:\n",
    "                        check_pos = grid[ni][nj]\n",
    "                        # 1. if is wall or is lock but no key, continue, no count\n",
    "                        if check_pos == '#' or (check_pos.isupper() and nstate[lock2idx[check_pos]] == '0'):\n",
    "                            continue\n",
    "\n",
    "\n",
    "                        # 2. if key, update state,\n",
    "                        if check_pos.islower():\n",
    "                            list_state = list(nstate)\n",
    "                            list_state[key2idx[check_pos]] = '1'\n",
    "                            nstate = ''.join(list_state)\n",
    "                            # print(nstate)\n",
    "                        \n",
    "\n",
    "\n",
    "                        # 3. if not visited, add to vis and add to q\n",
    "                        if (ni, nj, nstate) not in vis:\n",
    "                            vis.add((ni, nj, nstate))\n",
    "                            q.append((ni, nj, nstate))\n",
    "            # complete one layer\n",
    "            step += 1\n",
    "\n",
    "        return -1 \n",
    "\n",
    "                    \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n, ks = len(grid), len(grid[0]), {}\n",
    "        visited, stack = set(), collections.deque()\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c] == '@': stack.append([r, c, 0, 0])\n",
    "                elif grid[r][c] not in {'.', '#'}:\n",
    "                    if grid[r][c].islower() and not grid[r][c] in ks:\n",
    "                        ks[grid[r][c]] = len(ks)\n",
    "        drcs, tar = [[1, 0], [-1, 0], [0, 1], [0, -1]], (1 << len(ks)) - 1\n",
    "        while stack:\n",
    "            r, c, st, val = stack.popleft()\n",
    "            if not (r, c, st) in visited:\n",
    "                visited.add((r, c, st))\n",
    "                if st == tar: return val\n",
    "                for dr, dc in drcs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if -1 < nr < m and -1 < nc < n:\n",
    "                        if grid[nr][nc] == '#': continue\n",
    "                        elif grid[nr][nc] in {'.', '@'}:\n",
    "                            stack.append([nr, nc, st, val + 1])\n",
    "                        else:\n",
    "                            l = grid[nr][nc]\n",
    "                            idx = ks[l.lower()]\n",
    "                            ns = st\n",
    "                            if l.islower(): ns |= (1 << idx)\n",
    "                            elif (st & (1 << idx)) == 0: continue\n",
    "                            stack.append([nr, nc, ns, val + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m, n, ks = len(grid), len(grid[0]), {}\n",
    "        visited, stack = set(), collections.deque()\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c] == '@': stack.append([r, c, 0, 0])\n",
    "                elif grid[r][c] not in {'.', '#'}:\n",
    "                    if grid[r][c].islower() and not grid[r][c] in ks:\n",
    "                        ks[grid[r][c]] = len(ks)\n",
    "        drcs, tar = [[1, 0], [-1, 0], [0, 1], [0, -1]], (1 << len(ks)) - 1\n",
    "        while stack:\n",
    "            r, c, st, val = stack.popleft()\n",
    "            if not (r, c, st) in visited:\n",
    "                visited.add((r, c, st))\n",
    "                if st == tar: return val\n",
    "                for dr, dc in drcs:\n",
    "                    nr, nc = r + dr, c + dc\n",
    "                    if -1 < nr < m and -1 < nc < n:\n",
    "                        if grid[nr][nc] == '#': continue\n",
    "                        elif grid[nr][nc] in {'.', '@'}:\n",
    "                            stack.append([nr, nc, st, val + 1])\n",
    "                        else:\n",
    "                            l = grid[nr][nc]\n",
    "                            idx = ks[l.lower()]\n",
    "                            ns = st\n",
    "                            if l.islower(): ns |= (1 << idx)\n",
    "                            elif (st & (1 << idx)) == 0: continue\n",
    "                            stack.append([nr, nc, ns, val + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        si, sj = next((i,j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "\n",
    "        n_keys = sum(grid[i][j].islower() for i in range(m) for j in range(n))\n",
    "\n",
    "        n_locks = n_keys\n",
    "\n",
    "        locks = ['A', 'B', 'C', 'D', 'E', 'F']\n",
    "        lock2idx = {}\n",
    "        key2idx = {}\n",
    "        for i, key in enumerate(locks):\n",
    "            lock2idx[key] = i\n",
    "            key2idx[key.lower()] = i\n",
    "\n",
    "        \n",
    "\n",
    "        visited = set()\n",
    "        q = deque()\n",
    "\n",
    "        q.append((si, sj, '0'*n_keys))\n",
    "        visited.add((si, sj, '0'*n_keys))\n",
    "        steps = 0\n",
    "\n",
    "        # dirs\n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        while q:\n",
    "            for _ in range(len(q)): # for shortest path\n",
    "\n",
    "                i, j, state = q.popleft()\n",
    "\n",
    "                # break condition\n",
    "                if state == '1'*n_keys:\n",
    "                    return steps\n",
    "\n",
    "\n",
    "                for a, b in pairwise(dirs):\n",
    "                    ni, nj, nstate = i+a, j+b, state\n",
    "                    \n",
    "                    # in range\n",
    "                    if 0<=ni<m and 0<=nj<n:\n",
    "                        x = grid[ni][nj]\n",
    "\n",
    "                        # invalid\n",
    "                        # hit walls or hit a lock but no key\n",
    "                        if x == '#' or (x.isupper() and nstate[lock2idx[x]] == '0'):\n",
    "                            continue\n",
    "\n",
    "                        # valid and state needs to be updated\n",
    "                        if x.islower():\n",
    "                            tmp = list(nstate)\n",
    "                            tmp[key2idx[x]] = '1'\n",
    "                            nstate = ''.join(tmp)\n",
    "\n",
    "\n",
    "\n",
    "                        # if not visited< load to q\n",
    "                        if (ni, nj, nstate) not in visited: \n",
    "                            visited.add((ni, nj, nstate))\n",
    "                            q.append((ni, nj, nstate))\n",
    "            steps += 1\n",
    "                \n",
    "\n",
    "        return -1\n",
    "                \n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # range\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "\n",
    "        # find start\n",
    "        si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # dirs \n",
    "        dirs = (-1, 0, 1, 0, -1)\n",
    "        locks = ['A', 'B', 'C', 'D', 'E', 'F']\n",
    "        lock2pos = {key_let: i for i, key_let in enumerate(locks)}\n",
    "        key2pos = {key_let.lower(): i for i, key_let in enumerate(locks)}\n",
    "        total_num_keys = sum(grid[i][j].islower() for i in range(m) for j in range(n))\n",
    "        key_checker = '0'*total_num_keys\n",
    "\n",
    "        q = deque()\n",
    "        q.append((si, sj, key_checker))\n",
    "\n",
    "        visited = set()\n",
    "        visited.add((si, sj, key_checker))\n",
    "        res = 0\n",
    "\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j, state = q.popleft()\n",
    "\n",
    "                # break condition\n",
    "                if state == '1'*total_num_keys:\n",
    "                    return res\n",
    "                # search\n",
    "                for a, b in pairwise(dirs):\n",
    "                    ni, nj, nstate = i+a, j+b, state\n",
    "                    if 0<=ni<m and 0<=nj<n: # works only with valid map\n",
    "\n",
    "                        # hit wall or hit lock but no key\n",
    "                        if grid[ni][nj] == \"#\" or (grid[ni][nj].isupper() and state[lock2pos[grid[ni][nj]]] == '0'):\n",
    "                            continue\n",
    "\n",
    "\n",
    "                        # hit key and update states\n",
    "                        if grid[ni][nj].islower():\n",
    "                            tmp = list(nstate)\n",
    "                            tmp[key2pos[grid[ni][nj]]] = '1'\n",
    "                            nstate = ''.join(tmp)\n",
    "\n",
    "\n",
    "                        # if ( i,j, current state) is not visited \n",
    "                        if (ni, nj, nstate) not in visited:\n",
    "                            visited.add((ni, nj, nstate))\n",
    "                            q.append((ni, nj, nstate))\n",
    "            res += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # # range\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        \n",
    "\n",
    "        # # find start\n",
    "        # si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # # dirs \n",
    "        # dirs = (-1, 0, 1, 0, -1)\n",
    "\n",
    "        # # nkeys\n",
    "        # nkeys = sum(grid[i][j].islower() for i in range(m) for j in range(n))\n",
    "\n",
    "        # # state\n",
    "        # visited = set()\n",
    "        # visited.add((si, sj, '0'*nkeys)) # we use 0 to indicate it's not visited, we use 1 to indicate visited and already grabed the key\n",
    "\n",
    "        # # queue\n",
    "        # q = deque()\n",
    "        # q.append((si, sj, '0'*nkeys)) # here is the state and the above is the visited \n",
    "\n",
    "\n",
    "        # keys = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "        # check = {key: i for i, key in enumerate(keys)}\n",
    "\n",
    "        # out = 0\n",
    "        # while q:\n",
    "        #     for _ in range(len(q)): #We need to fninish all directions in a layer\n",
    "        #         i, j, state = q.popleft()\n",
    "        #         # break condition (final and invalid)\n",
    "        #         if state == '1'*nkeys:\n",
    "        #             return out\n",
    "\n",
    "        #         for a, b in pairwise(dirs):\n",
    "        #             ni, nj = i+a, j+b\n",
    "        #             nstate = state # this is important as we usually don't want to mess up with the previous state\n",
    "\n",
    "        #             # wihtin range\n",
    "        #             if 0<=ni<m and 0<=nj<n:\n",
    "        #                 # if not satisfied (1. hit wall, meet lock and no currresponding key)\n",
    "        #                 if grid[ni][nj] == '#' or (grid[ni][nj].isupper() and nstate[check[grid[ni][nj].lower()]] == '0'):\n",
    "        #                     continue\n",
    "\n",
    "\n",
    "        #                 # if satisfied, update state: pickup the key\n",
    "        #                 if grid[ni][nj].islower():\n",
    "        #                     # print(check[grid[ni][nj].lower()])\n",
    "        #                     tmp = list(nstate)\n",
    "        #                     tmp[check[grid[ni][nj].lower()]] = '1'\n",
    "        #                     nstate = ''.join(tmp)\n",
    "        #                     # pass\n",
    "\n",
    "\n",
    "        #                 # register new visits and queue\n",
    "        #                 if (ni, nj, nstate) not in visited:\n",
    "        #                     q.append((ni, nj, nstate))\n",
    "        #                     visited.add((ni, nj, nstate))\n",
    "\n",
    "        #     out += 1\n",
    "\n",
    "        # return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        # # size\n",
    "        # m = len(grid)\n",
    "        # n = len(grid[0])\n",
    "\n",
    "\n",
    "        # # find start\n",
    "        # si, sj = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == '@')\n",
    "\n",
    "        # #set buffer\n",
    "        # key_tot = sum(v.islower() for row in grid for v in row)\n",
    "        # all_pos = ['A', 'B', 'C', 'D', 'E', 'F']\n",
    "        # key_in_consider = all_pos[:key_tot]\n",
    "        # # lock2idx\n",
    "        # lock2idx = {cur: i for i, cur in enumerate(key_in_consider)}\n",
    "        # all_pos = ['a', 'b', 'c', 'd', 'e', 'f']\n",
    "        # key_in_consider = all_pos[:key_tot]\n",
    "        # key2idx = {cur: i for i, cur in enumerate(key_in_consider)}\n",
    "        \n",
    "        # keys = '0' * key_tot # == 1 for has this key == 0 for not having this key\n",
    "        # vis = {(si, sj, keys)} # location i, location j, key status (initially no keys obtained)\n",
    "        # # this is different as not only the location but also the status of the keys need to be registered \n",
    "        # step = 0 # final output\n",
    "\n",
    "        # dirs = (-1, 0, 1, 0, -1) # all possible directions (dirs[i], dirs[i+1]) for i in range(4)\n",
    "        # q = deque([(si, sj, keys)])\n",
    "\n",
    "        # while q:\n",
    "        #     for _ in range(len(q)): # needs to consider the shortest path so each layer is counted only once            \n",
    "\n",
    "        #         i, j, state = q.popleft()\n",
    "        #         # print(state)\n",
    "        #         if state == '1'*key_tot: # output condition\n",
    "        #             return step\n",
    "                \n",
    "        #         for a, b in pairwise(dirs):\n",
    "        #             ni, nj = i + a, j + b\n",
    "        #             nstate = state\n",
    "        #             # now decide if the new location and state are valid\n",
    "\n",
    "        #             # only consider the case when the steps are in the grid\n",
    "        #             if 0 <= ni < m and 0 <= nj < n:\n",
    "        #                 check_pos = grid[ni][nj]\n",
    "        #                 # 1. if is wall or is lock but no key, continue, no count\n",
    "        #                 if check_pos == '#' or (check_pos.isupper() and nstate[lock2idx[check_pos]] == '0'):\n",
    "        #                     continue\n",
    "\n",
    "\n",
    "        #                 # 2. if key, update state,\n",
    "        #                 if check_pos.islower():\n",
    "        #                     list_state = list(nstate)\n",
    "        #                     list_state[key2idx[check_pos]] = '1'\n",
    "        #                     nstate = ''.join(list_state)\n",
    "        #                     # print(nstate)\n",
    "                        \n",
    "\n",
    "\n",
    "        #                 # 3. if not visited, add to vis and add to q\n",
    "        #                 if (ni, nj, nstate) not in vis:\n",
    "        #                     vis.add((ni, nj, nstate))\n",
    "        #                     q.append((ni, nj, nstate))\n",
    "        #     # complete one layer\n",
    "        #     step += 1\n",
    "\n",
    "        # return -1 \n",
    "\n",
    "                    \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expand(self, x, y, s, ss, step):\n",
    "        if self.grid[x][y] != '#':\n",
    "            if self.grid[x][y] == '.' or self.grid[x][y] == '@':\n",
    "                if not self.valid[x][y][s]:\n",
    "                    self.valid[x][y][s] = True\n",
    "                    self.dq.append([x, y, s, step])\n",
    "            elif self.grid[x][y] in self.keys_idxs:\n",
    "                idx = self.keys_idxs[self.grid[x][y]]\n",
    "                if ss[idx] == '0':\n",
    "                    ss_new = ss[:idx] + '1' + ss[idx+1:]\n",
    "                    s = self.statusFlatMerge(ss_new)\n",
    "                if not self.valid[x][y][s]:\n",
    "                    self.valid[x][y][s] = True\n",
    "                    self.dq.append([x, y, s, step])\n",
    "            else:\n",
    "                idx = self.keys_idxs[self.grid[x][y].lower()]\n",
    "                if ss[idx] != '0':\n",
    "                    ss_new = ss[:idx] + '2' + ss[idx+1:]\n",
    "                    s = self.statusFlatMerge(ss_new)\n",
    "                    if not self.valid[x][y][s]:\n",
    "                        self.valid[x][y][s] = True\n",
    "                        self.dq.append([x, y, s, step])\n",
    "\n",
    "\n",
    "\n",
    "    def visit(self, posi, ss):\n",
    "        x, y, s, step = posi\n",
    "        if x > 0:\n",
    "            self.expand(x-1, y, s, ss, step+1)\n",
    "        if x < self.m - 1:\n",
    "            self.expand(x+1, y, s, ss, step+1)\n",
    "        if y > 0:\n",
    "            self.expand(x, y-1, s, ss, step+1)\n",
    "        if y < self.n - 1:\n",
    "            self.expand(x, y+1, s, ss, step+1)\n",
    "\n",
    "\n",
    "    def statusFlatten(self, s):\n",
    "        ss = ''\n",
    "        for i in range(self.ksize):\n",
    "            ss += str(s % 3)\n",
    "            s //= 3\n",
    "        return ss\n",
    "    \n",
    "    def statusFlatMerge(self, ss):\n",
    "        s = 0\n",
    "        base = 1\n",
    "        for char in ss:\n",
    "            s += base * int(char)\n",
    "            base *= 3\n",
    "        return s\n",
    "\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        self.grid = grid\n",
    "        self.keys_list = []\n",
    "        self.keys_idxs = dict()\n",
    "        lowlet_lidx, lowlet_ridx = ord('a'), ord('z')\n",
    "        self.dlow_high = ord('A') - ord('a')\n",
    "        self.m, self.n = len(grid), len(grid[0])\n",
    "        sx, sy = None, None\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                gidx = ord(grid[i][j])\n",
    "                if gidx >= lowlet_lidx and gidx <= lowlet_ridx:\n",
    "                    self.keys_list.append(grid[i][j])\n",
    "                if grid[i][j] == '@':\n",
    "                    sx, sy = i, j\n",
    "        for i, key in enumerate(self.keys_list):\n",
    "            self.keys_idxs[key] = i\n",
    "        self.ssize = 3 ** len(self.keys_list)\n",
    "        self.ksize = len(self.keys_list)\n",
    "        self.valid = [[[False for _ in range(self.ssize)] for __ in range(self.n)] for ___ in range(self.m)]\n",
    "        self.valid[sx][sy][0] = True\n",
    "        self.dq = collections.deque()\n",
    "        self.dq.append([sx, sy, 0, 0]) # x, y, status, step\n",
    "        while len(self.dq) > 0:\n",
    "            ele = self.dq.popleft()\n",
    "            x, y, s, step = ele\n",
    "            ss = self.statusFlatten(s)\n",
    "            if '0' not in ss:\n",
    "                return step\n",
    "            self.visit(ele, ss)\n",
    "            # print(ele, ss)\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        key_names = set()\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        start_x, start_y = None, None\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j].islower():\n",
    "                    key_names.add(grid[i][j])\n",
    "                if grid[i][j] == '@':\n",
    "                    start_x, start_y = i, j\n",
    "        k = len(key_names)\n",
    "\n",
    "        q = collections.deque([])\n",
    "        visited = set()\n",
    "\n",
    "        q.append([0, start_x, start_y])\n",
    "        visited.add((start_x, start_y))\n",
    "        while len(q)>0:\n",
    "            # print(q)\n",
    "            state = q.popleft()\n",
    "            # print(state)\n",
    "            num_steps = state[0]\n",
    "            cur_x, cur_y = state[1], state[2]\n",
    "            keys = state[3:]\n",
    "\n",
    "            if len(keys) == k:\n",
    "                return num_steps\n",
    "            for dx,dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                nxt_x, nxt_y = cur_x+dx, cur_y+dy\n",
    "                # print(nxt_x, nxt_y)\n",
    "                if nxt_x>=0 and nxt_y>=0 and \\\n",
    "                    nxt_x<n and nxt_y<m and \\\n",
    "                    grid[nxt_x][nxt_y] != \"#\":\n",
    "                    if grid[nxt_x][nxt_y].isupper() and grid[nxt_x][nxt_y].lower() not in keys:\n",
    "                        continue\n",
    "                    new_keys = keys.copy()\n",
    "                    if grid[nxt_x][nxt_y].islower() and grid[nxt_x][nxt_y] not in keys:\n",
    "                        new_keys.append( grid[nxt_x][nxt_y])\n",
    "                        new_keys.sort()      \n",
    "                    new_state = tuple([nxt_x, nxt_y]+new_keys)\n",
    "                    # print(new_state)\n",
    "                    if new_state in visited:\n",
    "                        continue\n",
    "                    visited.add(new_state)\n",
    "                    q.append([num_steps+1, nxt_x, nxt_y]+new_keys)\n",
    "        return -1\n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        for i in range(n):\n",
    "            grid[i] = list(grid[i])\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        quene = [[0,0,0] for _ in range(31*31*2**6)]\n",
    "        visited = [[[False for _ in range(2**6)] for _ in range(31)] for _ in range(31)]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        key = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '@':\n",
    "                    quene[r][0] = i\n",
    "                    quene[r][1] = j\n",
    "                    quene[r][2] = 0\n",
    "                    r += 1\n",
    "                if grid[i][j] <= 'f' and grid[i][j] >= 'a':\n",
    "                    key |= 1 << (ord(grid[i][j]) - ord('a'))\n",
    "        level = 1\n",
    "        while l < r:\n",
    "            for _ in range(r-l):\n",
    "                x = quene[l][0]\n",
    "                y = quene[l][1]\n",
    "                s = quene[l][2]\n",
    "                l += 1\n",
    "                for i in range(4):\n",
    "                    nx = x + move[i]\n",
    "                    ny = y + move[i+1]\n",
    "                    ns = s\n",
    "                    if nx < 0 or nx == n or ny < 0 or ny == m or grid[nx][ny] == '#':\n",
    "                        continue\n",
    "                    if grid[nx][ny] <= 'F' and grid[nx][ny] >= 'A' and (s & (1 << (ord(grid[nx][ny]) - ord('A')))) == 0:\n",
    "                        continue\n",
    "                    if grid[nx][ny] <= 'f' and grid[nx][ny] >= 'a':\n",
    "                        ns |= (1 << (ord(grid[nx][ny]) - ord('a')))\n",
    "                    if ns == key:\n",
    "                        return level\n",
    "                    if not visited[nx][ny][ns]:\n",
    "                        quene[r][0] = nx\n",
    "                        quene[r][1] = ny\n",
    "                        quene[r][2] = ns\n",
    "                        r += 1\n",
    "                        visited[nx][ny][ns] = True\n",
    "            level += 1\n",
    "        return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        for i in range(n):\n",
    "            grid[i] = list(grid[i])\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        quene = [[0,0,0] for _ in range(31*31*2**6)]\n",
    "        visited = [[[False for _ in range(2**6)] for _ in range(31)] for _ in range(31)]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        key = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '@':\n",
    "                    quene[r][0] = i\n",
    "                    quene[r][1] = j\n",
    "                    quene[r][2] = 0\n",
    "                    r += 1\n",
    "                if grid[i][j] <= 'f' and grid[i][j] >= 'a':\n",
    "                    key |= 1 << (ord(grid[i][j]) - ord('a'))\n",
    "        level = 1\n",
    "        while l < r:\n",
    "            for _ in range(r-l):\n",
    "                x = quene[l][0]\n",
    "                y = quene[l][1]\n",
    "                s = quene[l][2]\n",
    "                l += 1\n",
    "                for i in range(4):\n",
    "                    nx = x + move[i]\n",
    "                    ny = y + move[i+1]\n",
    "                    ns = s\n",
    "                    if nx < 0 or nx == n or ny < 0 or ny == m or grid[nx][ny] == '#':\n",
    "                        continue\n",
    "                    if grid[nx][ny] <= 'F' and grid[nx][ny] >= 'A' and (s & (1 << (ord(grid[nx][ny]) - ord('A')))) == 0:\n",
    "                        continue\n",
    "                    if grid[nx][ny] <= 'f' and grid[nx][ny] >= 'a':\n",
    "                        ns |= (1 << (ord(grid[nx][ny]) - ord('a')))\n",
    "                    if ns == key:\n",
    "                        return level\n",
    "                    if not visited[nx][ny][ns]:\n",
    "                        quene[r][0] = nx\n",
    "                        quene[r][1] = ny\n",
    "                        quene[r][2] = ns\n",
    "                        r += 1\n",
    "                        visited[nx][ny][ns] = True\n",
    "            level += 1\n",
    "        return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        for i in range(n):\n",
    "            grid[i] = list(grid[i])\n",
    "        move = [-1, 0, 1, 0, -1]\n",
    "        quene = [[0,0,0] for _ in range(31*31*2**6)]\n",
    "        visited = [[[False for _ in range(2**6)] for _ in range(31)] for _ in range(31)]\n",
    "        l = 0\n",
    "        r = 0\n",
    "        key = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == '@':\n",
    "                    quene[r][0] = i\n",
    "                    quene[r][1] = j\n",
    "                    quene[r][2] = 0\n",
    "                    r += 1\n",
    "                if grid[i][j] <= 'f' and grid[i][j] >= 'a':\n",
    "                    key |= 1 << (ord(grid[i][j]) - ord('a'))\n",
    "        level = 1\n",
    "        while l < r:\n",
    "            for _ in range(r-l):\n",
    "                x = quene[l][0]\n",
    "                y = quene[l][1]\n",
    "                s = quene[l][2]\n",
    "                l += 1\n",
    "                for i in range(4):\n",
    "                    nx = x + move[i]\n",
    "                    ny = y + move[i+1]\n",
    "                    ns = s\n",
    "                    if nx < 0 or nx == n or ny < 0 or ny == m or grid[nx][ny] == '#':\n",
    "                        continue\n",
    "                    if grid[nx][ny] <= 'F' and grid[nx][ny] >= 'A' and (s & (1 << (ord(grid[nx][ny]) - ord('A')))) == 0:\n",
    "                        continue\n",
    "                    if grid[nx][ny] <= 'f' and grid[nx][ny] >= 'a':\n",
    "                        ns |= (1 << (ord(grid[nx][ny]) - ord('a')))\n",
    "                    if ns == key:\n",
    "                        return level\n",
    "                    if not visited[nx][ny][ns]:\n",
    "                        quene[r][0] = nx\n",
    "                        quene[r][1] = ny\n",
    "                        quene[r][2] = ns\n",
    "                        r += 1\n",
    "                        visited[nx][ny][ns] = True\n",
    "            level += 1\n",
    "        return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestPathAllKeys(self, grid: List[str]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        locks = \"ABCDEF\"\n",
    "        keys = \"abcdef\"\n",
    "        totalKeys = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == '@':\n",
    "                    x = i\n",
    "                    y = j\n",
    "                if grid[i][j] in keys:\n",
    "                    totalKeys += 1\n",
    "\n",
    "        #注意Python中的双队列是怎样声明的！！！\n",
    "        q = deque([(x, y, '')])\n",
    "        print(x,y)\n",
    "        res = 0\n",
    "        dir = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        vis = set()\n",
    "\n",
    "        while q:\n",
    "            ###注意想清楚该题解是如何按照bfs按层求解的！！！小心！！！\n",
    "            for node in range(len(q)):\n",
    "                x, y, state = q.popleft()\n",
    "                #注意判断该state有没有在之前出现过！！！\n",
    "                if (x,y,state) in vis:\n",
    "                    continue\n",
    "                if len(state) == totalKeys:\n",
    "                    return res\n",
    "                #如果没有见过 要加入vis\n",
    "                #注意Python中加入集合的语法写法！！！\n",
    "                vis.add((x,y,state))\n",
    "                for dx,dy in dir:\n",
    "                    #小心！！！注意！！！不能直接用相同变量名！！！会导致累计相加！！！最终导致错误！！！\n",
    "                    xx = x + dx\n",
    "                    yy = y + dy\n",
    "                    print(x,y)\n",
    "                    if not (0 <= xx < m and 0 <= yy < n and grid[xx][yy] != '#'):\n",
    "                        continue\n",
    "                    #注意是grid[x][y]不是grid[i][j]!!!!\n",
    "                    if grid[xx][yy] in locks and grid[xx][yy].lower() in state:\n",
    "                        #注意！！！无论是q队列还是vis集合，加入的都是规定范式的三元组！！！三元组格式要前后对应上！！！\n",
    "                        q.append((xx,yy,state))\n",
    "                    elif grid[xx][yy] in keys:\n",
    "                        if grid[xx][yy] not in state:\n",
    "                            q.append((xx,yy,state+grid[xx][yy]))\n",
    "                        else:\n",
    "                            q.append((xx,yy,state))\n",
    "                    #别忘这一部分！！！\n",
    "                    elif grid[xx][yy] in '.@':\n",
    "                        q.append((xx,yy,state))\n",
    "            res += 1\n",
    "        return -1\n",
    "                    \n",
    "\n",
    "\n",
    "            \n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
